Given a sorted dictionary of an alien language having some words dict and k starting alphabets of a standard dictionary. Find the order of characters in the alien language. If no valid ordering of letters is possible, then return an empty string.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be "true" if the order of string returned by the function is correct else "false" denotes incorrect string returned
Input: dict = ["baa","abcd","abca","cab","cad"], k = 4
Output: true
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: dict = ["dhhid" "dahi" "cedg" "fg" "gdah" "i" "gbdei" "hbgf" "e" "ddde"], k = 9
Output: false
Company Tags: Google, Flipkart, Amazon, Microsoft, OYO Rooms, Walmart
Constraints:
1 ≤ dict.size()≤ 10^4
1 ≤ k ≤ 26
1 ≤ Length of words ≤ 50
Approach 1 : Using Topological Sort (BFS)
class KahnAlgorithm {
vector<vector<int>> adjList;
void createGraphFromUnmatchChar(const string& s1, const string& s2) {
int m = min(s1.size(), s2.size());
for(int j = 0; j < m; ++j) {
int u = s1[j] - 'a';
int v = s2[j] - 'a';
if(u != v) {
adjList[u].push_back(v);
break;
}
}
}
string BFS(int k) {
// Find the indegree of nodes
vector<int> indegree(k);
for(int node = 0; node < k; ++node)
for(int neighbor : adjList[node])
indegree[neighbor]++;
// Push the root nodes to queue
queue<int> q;
for(int node = 0; node < k; ++node)
if(indegree[node] == 0)
q.push(node);
string topologicalOrder;
while(!q.empty()) {
int node = q.front(); q.pop();
topologicalOrder.push_back(node + 'a');
for(int neighbor : adjList[node]) {
if(--indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
if(topologicalOrder.size() == k)
return topologicalOrder;
return {}; // If a cycle is detected
}
public:
// O(N+K+E) & O(K+E) : Where N = size of dict, K = total nodes, E = total edges.
string getAlienLanguage(vector<string>& dict, int k) {
int n = dict.size();
adjList.resize(k);
// Build the adjacency list
for(int i = 0; i < n-1; ++i)
createGraphFromUnmatchChar(dict[i], dict[i + 1]);
return BFS(k);
}
};Approach 2 : Using Topological Sort (DFS)
class TopoSortDFS {
vector<vector<int>> adjList;
void createGraphFromUnmatchChar(const string& s1, const string& s2) {
int m = min(s1.size(), s2.size());
for(int j = 0; j < m; ++j) {
int u = s1[j] - 'a';
int v = s2[j] - 'a';
if(u != v) {
adjList[u].push_back(v);
break;
}
}
}
void DFS(int node, vector<bool>& visited, string& topologicalOrder) {
visited[node] = true;
for(int neighbor : adjList[node])
if(!visited[neighbor])
DFS(neighbor, visited, topologicalOrder);
topologicalOrder.push_back(node + 'a');
}
public:
// O(N+K+E) & O(K+E) : Where N = size of dict, K = total nodes, E = total edges.
string getAlienLanguage(vector<string>& dict, int k) {
int n = dict.size();
adjList.resize(k);
// Build the adjacency list
for(int i = 0; i < n-1; ++i)
createGraphFromUnmatchChar(dict[i], dict[i + 1]);
vector<bool> visited(k); // Helps to visit all components of graph. Assuming the graph has disconnected components
string topologicalOrder;
for(int node = 0; node < k; ++node)
if(!visited[node])
DFS(node, visited, topologicalOrder);
reverse(begin(topologicalOrder), end(topologicalOrder));
return topologicalOrder;
}
};Approach 3 : Using Topo Sort (DFS + Handling Cycles / Ignoring The Problem Note)
class TopoSortDFSCycles {
vector<vector<int>> adjList;
void createGraphFromUnmatchChar(const string& s1, const string& s2) {
int m = min(s1.size(), s2.size());
for(int j = 0; j < m; ++j) {
int u = s1[j] - 'a';
int v = s2[j] - 'a';
if(u != v) {
adjList[u].push_back(v);
break;
}
}
}
bool isCycle(int node, vector<bool>& visited, vector<bool>& inStack, string& topologicalOrder) {
visited[node] = inStack[node] = true;
for(int neighbor : adjList[node]) {
if(visited[neighbor] && !inStack[neighbor])
continue; // If the neighbour is already visited and currently while visiting again its not in the stack then we never got cycle from its path
if(inStack[neighbor] || isCycle(neighbor, visited, inStack, topologicalOrder))
return true; // If the neighbour is already in stack then its visited again hence a cycle is present
}
topologicalOrder.push_back(node + 'a');
inStack[node] = false;
return false;
}
public:
// O(N+K+E) & O(K+E) : Where N = size of dict, K = total nodes, E = total edges.
string getAlienLanguage(vector<string>& dict, int k) {
int n = dict.size();
adjList.resize(k);
// Build the adjacency list
for(int i = 0; i < n-1; ++i)
createGraphFromUnmatchChar(dict[i], dict[i + 1]);
vector<bool> visited(k); // Helps to visit all components of graph. Assuming the graph has disconnected components
vector<bool> inStack(k); // Tracks the nodes lying in the recursion stack
string topologicalOrder;
for(int node = 0; node < k; ++node)
if(!visited[node] && isCycle(node, visited, inStack, topologicalOrder))
return {}; // If a cycle is detected
reverse(begin(topologicalOrder), end(topologicalOrder));
return topologicalOrder;
}
};Note: I originally solved this problem on another coding platform, and the constraints, company tags and inputs provided in this are derived from there. However, due to LeetCode guidelines, I cannot link to the original post.
𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍