Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.
Examples :
Input: N = 5, K = 4, dict = {"baa","abcd","abca","cab","cad"}
Output: 1
Explanation: Here order of characters is 'b', 'd', 'a', 'c' Note that words are sorted and in the given language "baa" comes before "abcd", therefore 'b' is before 'a' in output.
Similarly we can find other orders.
Input: N = 3, K = 3, dict = {"caa","aaa","aab"}
Output: 1
Explanation: Here order of characters is 'c', 'a', 'b' Note that words are sorted and in the given language "caa" comes before "aaa", therefore 'c' is before 'a' in output.
Similarly we can find other orders.
Expected Time Complexity: O(N * |S| + K) , where |S| denotes maximum length.
Expected Space Compelxity: O(K)
Constraints:
1 ≤ N≤ 104
1 ≤ K ≤ 26
1 ≤ Length of words ≤ 50
Approach 01:
-
C++
-
Python
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Solution {
public:
string findOrder(string alienDictionary[], int numWords, int numCharacters) {
// Create an adjacency list for the graph where each character maps to a set of characters it precedes
unordered_map<char, unordered_set<char>> adjacencyList;
for (int i = 0; i < numWords; ++i) {
for (char c : alienDictionary[i]) {
adjacencyList[c]; // Ensure each character is in the adjacency list
}
}
// Build the graph based on the given order of words
for (int i = 0; i < numWords - 1; ++i) {
const string& word1 = alienDictionary[i];
const string& word2 = alienDictionary[i + 1];
int minLength = min(word1.length(), word2.length());
// Check for invalid input where word1 is longer but the prefix is the same
if (word1.length() > word2.length() && word1.substr(0, minLength) == word2.substr(0, minLength)) {
return ""; // Invalid ordering
}
// Find the first different character and update the adjacency list
for (int j = 0; j < minLength; ++j) {
if (word1[j] != word2[j]) {
adjacencyList[word1[j]].insert(word2[j]);
break;
}
}
}
// Set to track visited nodes and vector to store the topological order
unordered_set<char> visited;
vector<char> topologicalOrder;
// Perform topological sort using DFS
for (const auto& pair : adjacencyList) {
char charNode = pair.first;
if (visited.find(charNode) == visited.end()) {
performTopologicalSort(charNode, visited, topologicalOrder, adjacencyList);
}
}
// Return the reversed topological order to get the correct character order
reverse(topologicalOrder.begin(), topologicalOrder.end());
return string(topologicalOrder.begin(), topologicalOrder.end());
}
private:
// Perform a DFS-based topological sort
void performTopologicalSort(char node, unordered_set<char>& visited, vector<char>& topologicalOrder,
const unordered_map<char, unordered_set<char>>& adjacencyList) {
if (visited.find(node) != visited.end()) {
return;
}
visited.insert(node);
for (char neighbor : adjacencyList.at(node)) {
performTopologicalSort(neighbor, visited, topologicalOrder, adjacencyList);
}
topologicalOrder.push_back(node);
}
};
from typing import List
class Solution:
def findOrder(self, alienDictionary, numWords, numCharacters):
# Create a graph with each character mapping to a set of characters it comes before
adjacencyList = {char: set() for word in alienDictionary for char in word}
# Build the graph based on the given order of words
for i in range(numWords - 1):
word1, word2 = alienDictionary[i], alienDictionary[i + 1]
minLength = min(len(word1), len(word2))
# Check for invalid input where word1 is longer but the prefix is the same
if len(word1) > len(word2) and word1[:minLength] == word2[:minLength]:
return ""
# Find the first different character and build the adjacency list
for j in range(minLength):
if word1[j] != word2[j]:
adjacencyList[word1[j]].add(word2[j])
break
# Set to track visited nodes and list to store the topological order
visited = set()
topologicalOrder = []
def topologicalSort(node):
if node in visited:
return True
visited.add(node)
for neighbor in adjacencyList[node]:
topologicalSort(neighbor)
topologicalOrder.append(node)
return True
# Perform topological sort for each character in the graph
for char in adjacencyList:
topologicalSort(char)
# Return the reversed topological order to get the correct character order
return topologicalOrder[::-1]
Time Complexity
- Building the Adjacency List:
Constructing the adjacency list takes \( O(\text{numEdges}) \) time, as we iterate through each edge and add it to the list.
- Breadth-First Search (BFS):
BFS traverses each node and edge once. The time complexity of BFS is \( O(\text{numNodes} + \text{numEdges}) \), where \( \text{numNodes} \) is the number of nodes and \( \text{numEdges} \) is the number of edges.
- Overall Time Complexity:
The overall time complexity is \( O(\text{numNodes} + \text{numEdges}) \), combining the time to build the adjacency list and perform BFS.
Space Complexity
- Adjacency List:
The adjacency list requires \( O(\text{numNodes} + \text{numEdges}) \) space. Each node’s adjacency list stores all its edges, summing up to the total number of edges.
- Distance Array:
The distance array requires \( O(\text{numNodes}) \) space to store the shortest path distances for each node.
- Queue:
The queue used in BFS can hold up to \( O(\text{numNodes}) \) nodes at a time in the worst case.
- Overall Space Complexity:
The overall space complexity is \( O(\text{numNodes} + \text{numEdges}) \), combining the space for the adjacency list, distance array, and BFS queue.