# Alien Dictionary LeetCode Solution

Difficulty Level Hard
RubirkViews 2069

## Problem Statement

Alien Dictionary LeetCode Solution – There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings `words` from the alien language’s dictionary, where the strings in `words` are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return `""`. If there are multiple solutions, return any of them.

A string `s` is lexicographically smaller than a string `t` if at the first letter where they differ, the letter in `s` comes before the letter in `t` in the alien language. If the first `min(s.length, t.length)` letters are the same, then `s` is smaller if and only if `s.length < t.length`.

## Example

### Input:

words = [“wrt”, “wrf”, “er”, “ett”, “rftt”]

“wertf”

### Input:

words = [“z”, “x”, “z”]

“”

## Explanation

i) In the first test case, “wertf” is the correct string possible.

ii) In the second test case, the order is invalid, so return “”.

## Approach:

Let’s understand the problem statement first

1. words are sorted lexicographically which means if `W[i]` appears in the dictionary before `W[j]` for `i < j`.
2. Please note that `individual words are not sorted`. If `abcde` appears before `abpqrst` that doesn’t mean `b` appears before `a`.

Main things to note:

1. In a dictionary of words, for any two consecutive words, the order is decided by looking at the first uncommon char.

2. The chars following the uncommon char can’t be relied upon to conclude in any order. The reason being the order between the words was decided purely based on the first mismatching char, so any char after that is only there to constitute the complete word.

3. The consecutive chars appearing in any word has nothing to do with the order but they are there just to form the complete word.

Approach:

1. Create Graph: Using the above points, we iterate through consecutive word pairs and try to create edges.

2. Topological Sort: This can be done using DFS or BFS. I decided to go with BFS here

Edge cases

1. `["abc", "ab"]` – it’s not a valid dictionary, if `W[i] < W[j]` in the dictionary then `W[j]` can not be `prefix` of `W[i]`. so in this case simply return an empty string.
2. `["a", "b", "a"]` – here in this input, `a < b` and `b < a`, which is a cycle. a dictionary can not contain a cycle.

## Code for Alien Dictionary

### C++ Program

```class Solution {
public:
// Finds the topological order of a directed Acyclic graph
string topologicalSortBFS(unordered_map<char, unordered_set<char>> &g) {
unordered_map<char, int> indegree;
queue<char> q;
// topological order
string order;

// Compute the indegree of each node
for(auto u: g) {
char src = u.first;
for(auto neighbor: g[src])
++indegree[neighbor];
}

// if current has no dependency, add and mark as visited
for(auto u: g) {
char src = u.first;
if(!indegree[src]) {
q.emplace(src);
}
}
// BFS traversal wrt to indegree of each node
while(!q.empty()) {
auto curr = q.front();
q.pop();
order += curr;

// reduce the indegree of its neighbors
for(auto neighbor: g[curr]) {
--indegree[neighbor];
if(!indegree[neighbor])
q.emplace(neighbor);
}
}
return order.size() < g.size() ? "" : order;
}

string alienOrder(vector<string>& words) {
// create a graph
// To create a graph using the lexographic order,
// we need to look at the consecutive word pairs and
// within the common length check for diff chars at the same
// index position, each unequal pair is a directed edge coming
// from words[i][j] to words[i+1][j]
unordered_map<char, unordered_set<char>> g;
// initialize the graph with nodes req
for(auto &word: words)
for(char &ch: word)
if(!g.count(ch))
g[ch] = unordered_set<char>();

// Imp: Add all the seen chars to graph even with 0 edges
for(int w = 0; w + 1 < words.size(); w++) {
int common_len = min(words[w].size(), words[w+1].size());
// check if the lexographic order is being followed or not
// P.S I dont think this case is even valid acc to problem description
// Eg: ["abc", "ab"] -> Invalid
if(words[w+1].size() < words[w].size()
&& words[w].substr(0, common_len) == words[w+1])
return "";

for(int i = 0; i < common_len; i++) {
// prevent self loop
char src = words[w][i], dst = words[w+1][i];
// If current pos has diff chars, then make an edge and
// break since, the current word ordering was due this positional char
// change and anything beyond this might not follow actual order.
if(src != dst) {
g[src].emplace(dst);
break;
}
}
}

string order = topologicalSortBFS(g);
return order;
}
};```

### Java Program

```class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> dict = new HashMap<>();
Map<Character, Boolean> visited = new HashMap<>();

// add character to visited map, mark all of them as unvisited
for (String str: words) {
for (char ch: str.toCharArray()) {
visited.put(ch, false);
}
}

//
for (int i = 0; i < words.length-1; i++) {
if(!fillDict(dict, words[i], words[i+1])) {
// invalid input, ex:- ab,abc is not a valid dictionary word
return "";
}
}

StringBuilder builder = new StringBuilder();
for (char ch: visited.keySet()) {
if (!visited.get(ch)) {
// do the topological sorting from each unvisited dictionary character
if (!topological(dict, ch, visited, new HashSet<>(), builder)) {
// loop detected. topological sort can not be performed in graph with cycle
return "";
}
}
}
return builder.reverse().toString();
}

private boolean topological(Map<Character, Set<Character>> dict, char ch,
Map<Character, Boolean> visited,
Set<Character> dfsStack, StringBuilder builder) {
if (dfsStack.contains(ch)) {
// oops!! loop detected
return false;
}
if (visited.get(ch)) {
return true;
}
visited.put(ch, true);
for (char c : dict.getOrDefault(ch, new HashSet<>())) {
if (!topological(dict, c, visited, dfsStack, builder)) {
return false;
}
}
builder.append(ch);
dfsStack.remove(ch);
return true;
}

private boolean fillDict(Map<Character, Set<Character>> dict, String a, String b) {
for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
if (a.charAt(i) != b.charAt(i)) {
return true;
}
}
// minimum word is prefix of larger word, make sure word with less length comes before larger word
// why? because if one string is prefix of another then prefix must come before string for example,
// we are here becasue a,b = "abc" or "ab", since a is lexicographically smaller than b then a must
// be "ab" because "abc" can never come before "ab".
return a.length() <= b.length();
}
}```

## Complexity Analysis for Alien Dictionary LeetCode Solution

Time Complexity: O(V + E)

Space Complexity: O(V + E) for graph creation

Translate »