Solution: Alien Dictionary
Statement▼
You are given a list of words written in an alien language, where the words are sorted lexicographically by the rules of this language. Surprisingly, the aliens also use English lowercase letters, but possibly in a different order.
Given a list of words written in the alien language, return a string of unique letters sorted in the lexicographical order of the alien language as derived from the list of words.
If there’s no solution, that is, no valid lexicographical ordering, you can return an empty string "".
If multiple valid orderings exist, you may return any of them.
Note: A string,
a, is considered lexicographically smaller than stringbif:
At the first position where they differ, the character in
acomes before the character inbin the alien alphabet.If one string is a prefix of the other, the shorter string is considered smaller.
Constraints:
- 1≤
words.length≤103 - 1≤
words[i].length≤20 - All characters in
words[i]are English lowercase letters.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach is to generate all possible orders of alphabets in the alien language and then iterate over them, character by character, to select the ones that satisfy the dictionary dependencies. So, there’d be O(u!) permutations, where u is the number of unique alphabets in the alien language, and for each permutation, we’d have to check if it’s a valid partial order. That requires comparing against the dictionary words repeatedly.
This is very expensive since there are an exponential number of possible orders (u!) and only a handful of valid ones. On top of that, there’d be additional effort to compare them against the dictionary. The time complexity for this approach is O(u!). The space complexity is O(1).
Optimized approach using topological sort
We can solve this problem using the topological sort pattern. Topological sort is used to find a linear ordering of elements that have dependencies on or priority over each other. For example, if A is dependent on B or B has priority over A, then B is listed before A in topological order.
Using the list of words, we identify the relative precedence order of the letters in the words and generate a graph to represent this ordering. To traverse a graph, we can use breadth-first search to find the letters’ order.
We can essentially map this problem to a graph problem, but before exploring the exact details of the solution, there are a few things that we need to keep in mind:
-
The letters within a word don’t tell us anything about the relative order. For example, the word “educative” in the list doesn’t tell us that the letter “e” is before the letter “d.”
-
The input can contain words followed by their prefix, such as “educated” and then “educate.” These cases will never result in a valid alphabet because in a valid alphabet, prefixes are always first. We need to make sure our solution detects these cases correctly.
-
There can be more than one valid alphabet ordering. It’s fine for our algorithm to return any one of them.
-
The output dictionary must contain all unique letters within the words list, including those that could be in any position within the ordering. It shouldn’t contain any additional letters that weren’t in the input.
Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.
Step-by-step solution construction
For the graph problem, we can break this particular problem into three parts:
-
Extract the necessary information to identify the dependency rules from the words. For example, in the words [“patterns”, “interview”], the letter “p” comes before “i.”
-
With the gathered information, we can put these dependency rules into a directed graph with the letters as nodes and the dependencies (order) as the edges.
-
Lastly, we can sort the graph nodes topologically to generate the letter ordering (dictionary).
Let’s look at each part in more depth.
Part 1: Identifying the dependencies
Let’s start with example words and observe the initial ordering through simple reasoning:
["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu", "suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"]
As in the English language dictionary, where all the words starting with “a” come at the start followed by the words starting with “b,” “c,” “d,” and so on, we can expect the first letters of each word to be in alphabetical order.
["m", "m", "x", "x", "x", "x", "s", "s", "s", "s", "r", "r", "r"]
Removing the duplicates, we get the following:
["m", "x", "s", "r"]
Following the intuition explained above, we can assume that the first letters in the messages are in alphabetical order:
Looking at the letters above, we know the relative order of these letters, but we don’t know how these letters fit in with the rest of the letters. To get more information, we need to look further into our English dictionary analogy. The word “dirt” comes before “dorm.” This is because we look at the second letter when the first letter is the same. In this case, “i” comes before “o” in the alphabet.
We can apply the same logic to our alien words and look at the first two words, “mzsor” and “mqov.” As the first letter is the same in both words, we look at the second letter. The first word has “z,” and the second one has “q.” Therefore, we can safely say that “z” comes before “q” in this alien language. We now have two fragments of the letter order:
Note: Notice that we didn’t mention rules such as “m -> a”. This is fine because we can derive this relation from “m -> x”, “x -> a”.
This is it for the first part. Let’s put the pieces that we have in place.
Part 2: Representing the dependencies
We now have a set of relations mentioning the relative order of the pairs of letters:
["z -> q", "m -> x", "x -> a", "x -> v", "x -> s", "z -> x", "v -> a", "s -> r", "o -> w"]
Now the question arises, how can we put these relations together? It might be tempting to start chaining all these together. Let’s look at a few possible chains:
We can observe from our chains above that some letters might appear in more than one chain, and putting the chains into the output list one after the other won’t work. Some of the letters might be duplicated and would result in an invalid ordering. Let’s try to visualize the relations better with the help of a graph. The nodes are the letters, and an edge between two letters, “x” and “y” represents that “x” is before “y” in the alien words.
Part 3: Generating the dictionary
As we can see from the graph, four of the letters have no incoming arrows. This means that there are no letters that have to come before any of these four.
Remember: There could be multiple valid dictionaries, and if there are, then it’s fine for us to return any of them.
Therefore, a valid start to the ordering we return would be as follows:
["o", "m", "u", "z"]
We can now remove these letters and edges from the graph because any other letters that required them first will now have this requirement satisfied.
There are now three new letters on this new graph that have no in arrows. We can add these to our output list.
["o", "m", "u", "z", "x", "q", "w"]
Again, we can remove these from the graph.
Then, we add the two new letters with no in arrows.
["o", "m", "u", "z", "x", "q", "w", "v", "s"]
This leaves the following graph:
We can place the final two letters in our output list and return the ordering:
["o", "m", "u", "z", "x", "q", "w", "v", "s", "a", "r"]
Let’s now review how we can implement this approach.
Identifying the dependencies and representing them in the form of a graph is pretty straightforward. We extract the relations and insert them into an adjacency list:
Next, we need to generate the dictionary from the extracted relations: identify the letters (nodes) with no incoming links. Identifying whether a particular letter (node) has any incoming links or not from our adjacency list format can be a little complicated. A naive approach is to repeatedly iterate over the adjacency lists of all the other nodes and check whether or not they contain a link to that particular node.
This naive method would be fine for our case, but perhaps we can do it more optimally.
An alternative is to keep two adjacency lists:
- One with the same contents as the one above.
- One reversed that shows the incoming links.
This way, every time we traverse an edge, we can remove the corresponding edge from the reversed adjacency list:
What if we can do better than this? Instead of tracking the incoming links for all the letters from a particular letter, we can track the count of how many incoming edges there are. We can keep the in-degree count of all the letters along with the forward adjacency list.
In-degree corresponds to the number of incoming edges of a node.
It will look like this:
Now, we can decrement the in-degree count of a node instead of removing it from the reverse adjacency list. When the in-degree of the node reaches 0, this represents that this particular node has no incoming links left.
We perform BFS on all the letters that are reachable, that is, the in-degree count of the letters is zero. A letter is only reachable once the letters that need to be before it have been added to the output, result.
We use a queue to keep track of reachable nodes and perform BFS on them. Initially, we put the letters that have zero in-degree count. We keep adding the letters to the queue as their in-degree counts become zero.
We continue this until the queue is empty. Next, we check whether all the letters in the words have been added to the output or not. This would only happen when some letters still have some incoming edges left, which means there is a cycle. In this case, we return an empty string.
Remember: There can be letters that don’t have any incoming edges. This can result in different orderings for the same set of words, and that’s all right.
Let’s try to visualize the algorithm with the help of a set of slides below:
Delving into the actual code, the first step is to count the number of unique letters in the words and initialize the graph.
We consider adjacent words at a time and compare them character by character. Let’s call them c and d for the first and second words, respectively. If at any point they aren’t the same, we add d to the adjacency list of c. If all characters match, we check if one word is a prefix of the other. If the second word is a prefix of the first word, a topological sorting isn’t possible and we return an empty string.
from collections import defaultdict, Counter, dequedef print_string_with_markers(strn, pValue):out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]return outdef print_array_with_markers(arr, pValue):out = "["for i in range(len(arr)):if i in pValue:out += '«'out += str(arr[i]) + '»' + ", "else:out += str(arr[i]) + ", "out = out[0:len(out) - 2]out += "]"return outdef alien_order(words):# Step 0: Create data structures and find all unique letters.adj_list = defaultdict(set)# counts stores the number of unique lettersprint("\n\tGetting unique characters")counts = Counter({c: 0 for word in words for c in word})print("\t\t", counts.keys(), sep="")# Step 1: We need to populate adj_list and counts.# For each pair of adjacent words...print("\n\tComparing adjacent words")outer = 0for word1, word2 in zip(words, words[1:]):print("\t\tLoop index: ", outer, sep="")print("\t\t", print_array_with_markers(words, [outer, outer+1]), sep="")outer += 1print("\t\tWords to compare: ", word1, ", ", word2, sep="")print("\t\tIterating the words")inner = 0for c, d in zip(word1, word2):print("\t\t\tInner loop index: ", inner)print("\t\t\t\tword1: ", print_string_with_markers(word1, inner), ", c = ", c, sep="")print("\t\t\t\tword2: ", print_string_with_markers(word2, inner), ", d = ", d, sep="")inner += 1if c != d:print("\t\t\t\tThe characters are not the same")if d not in adj_list[c]:print("\t\t\t\t\tAdding '", d, "' to ", c,"'s children: ", adj_list[c], " ⟶ ", sep="", end="")adj_list[c].add(d)print(adj_list[c])print("\t\t\t\t\tIncremeting count of '",d, "' ⟶ ", sep="", end="")counts[d] += 1print(counts)breakelse:print("\t\t\t\tBoth characters are the same: '",c, "', moving to the next character", sep="")else: # Check that second word isn't a prefix of first word.if len(word2) < len(word1):return ""# Driver codedef main():words = [["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu","suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],["vanilla", "alpine", "algor", "port","norm", "nylon", "ophellia", "hidden"],["passengers", "to", "the", "unknown"],["alpha", "bravo", "charlie", "delta"],["jupyter", "ascending"]]for i in range(len(words)):print(i + 1, ".\twords = ", words[i], sep="")print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")print("-"*100)if __name__ == "__main__":main()
The next step is to find all sources, that is, vertices with in-degree =0. These nodes are the first ones to be removed from our graph and added to the result list.
We remove the source and decrease the in-degree of its children by 1. If a child’s in-degree becomes 0, it becomes the new source. We repeat this step until all vertices have been visited and added to the result list.
from collections import defaultdict, Counter, dequedef print_string_with_markers(strn, pValue):out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]return outdef print_array_with_markers(arr, pValue):out = "["for i in range(len(arr)):if i in pValue:out += '«'out += str(arr[i]) + '»' + ", "else:out += str(arr[i]) + ", "out = out[0:len(out) - 2]out += "]"return outdef alien_order(words):# Step 0: Create data structures and find all unique letters.adj_list = defaultdict(set)# counts stores the number of unique lettersprint("\n\tGetting unique characters")counts = Counter({c: 0 for word in words for c in word})print("\t\t", counts.keys(), sep="")# Step 1: We need to populate adj_list and counts.# For each pair of adjacent words...print("\n\tComparing adjacent words")outer = 0for word1, word2 in zip(words, words[1:]):print("\t\tLoop index: ", outer, sep="")print("\t\t", print_array_with_markers(words, [outer, outer+1]), sep="")outer += 1print("\t\tWords to compare: ", word1, ", ", word2, sep="")print("\t\tIterating the words")inner = 0for c, d in zip(word1, word2):print("\t\t\tInner loop index: ", inner)print("\t\t\t\tword1: ", print_string_with_markers(word1, inner), ", c = ", c, sep="")print("\t\t\t\tword2: ", print_string_with_markers(word2, inner), ", d = ", d, sep="")inner += 1if c != d:print("\t\t\t\tThe characters are not the same")if d not in adj_list[c]:print("\t\t\t\t\tAdding '", d, "' to ", c,"'s children: ", adj_list[c], " ⟶ ", sep="", end="")adj_list[c].add(d)print(adj_list[c])print("\t\t\t\t\tIncremeting count of '",d, "' ⟶ ", sep="", end="")counts[d] += 1print(counts)breakelse:print("\t\t\t\tBoth characters are the same: '",c, "', moving to the next character", sep="")else: # Check that second word isn't a prefix of first word.if len(word2) < len(word1):return ""# Step 2: We need to repeatedly pick off nodes with an indegree of 0.result = []sources_queue = deque([c for c in counts if counts[c] == 0])print("\n\tRemoving the sources")print("\t\tSources: ", sources_queue, sep="")m = 0while sources_queue:print("\t\tLoop index: ", m, sep="")m += 1print("\t\t\tGetting the source by popping from the queue")print("\t\t\tSources: ", sources_queue, " ⟶ ", end="", sep="")c = sources_queue.popleft()print(sources_queue)print("\t\t\t\tSource: ", c)print("\t\t\t\tAppending to the result list: ",result, " ⟶ ", end="", sep="")result.append(c)print(result)print("\t\t\tUpdating the in-degrees of the children")print("\t\t\t\tSource: ", c, ", children: ", adj_list[c], sep="")n = 0for d in adj_list[c]:print("\t\t\t\tInner loop index: ", n)n += 1print("\t\t\t\t\tChild: ", d, sep="")print("\t\t\t\t\tDecrementing in-degree of ", d,": ", counts[d], " ⟶ ", counts[d] - 1, sep="")counts[d] -= 1if counts[d] == 0:print("\t\t\t\t\tSince in-degree of ", d," = 0, it's now a source.", sep="")print("\t\t\t\t\tAdding it to the sources queue: ",sources_queue, " ⟶ ", end="", sep="")sources_queue.append(d)print(sources_queue)# Driver codedef main():words = [["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu","suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],["vanilla", "alpine", "algor", "port","norm", "nylon", "ophellia", "hidden"],["passengers", "to", "the", "unknown"],["alpha", "bravo", "charlie", "delta"],["jupyter", "ascending"]]for i in range(len(words)):print(i + 1, ".\twords = ", words[i], sep="")print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")print("-"*100)if __name__ == "__main__":main()
Now, our algorithm runs as expected and returns an ordering of the alphabet in the alien language. However, it doesn’t cater to a cycle in the word order. Therefore, we add a conditional statement that checks if all the letters are in the result list. If not, we have a cycle.
from collections import defaultdict, Counter, dequedef print_string_with_markers(strn, pValue):out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]return outdef print_array_with_markers(arr, pValue):out = "["for i in range(len(arr)):if i in pValue:out += '«'out += str(arr[i]) + '»' + ", "else:out += str(arr[i]) + ", "out = out[0:len(out) - 2]out += "]"return outdef alien_order(words):# Step 0: Create data structures and find all unique letters.adj_list = defaultdict(set)print()# counts stores the number of unique lettersprint("\n\tGetting unique characters")counts = Counter({c: 0 for word in words for c in word})print("\t\t", counts.keys(), sep="")# Step 1: We need to populate adj_list and counts.# For each pair of adjacent words...print("\n\tComparing adjacent words")outer = 0for word1, word2 in zip(words, words[1:]):print("\t\tLoop index: ", outer, sep="")print("\t\t", print_array_with_markers(words, [outer, outer+1]), sep="")outer += 1print("\t\tWords to compare: ", word1, ", ", word2, sep="")print("\t\tIterating the words")inner = 0for c, d in zip(word1, word2):print("\t\t\tInner loop index: ", inner)print("\t\t\t\tword1: ", print_string_with_markers(word1, inner), ", c = ", c, sep="")print("\t\t\t\tword2: ", print_string_with_markers(word2, inner), ", d = ", d, sep="")inner += 1if c != d:print("\t\t\t\tThe characters are not the same")if d not in adj_list[c]:# print("\t\t\t\t\tAdding '", d, "' to ", c, "'s children: ", adj_list[c], " ⟶ ", sep="", end="")adj_list[c].add(d)print(adj_list[c])print("\t\t\t\t\tIncremeting count of '",d, "' ⟶ ", sep="", end="")counts[d] += 1print(counts)breakelse:print("\t\t\t\tBoth characters are the same: '",c, "', moving to the next character", sep="")else: # Check that second word isn't a prefix of first word.if len(word2) < len(word1):return ""# Step 2: We need to repeatedly pick off nodes with an indegree of 0.result = []sources_queue = deque([c for c in counts if counts[c] == 0])print("\n\tRemoving the sources")print("\t\tSources: ", sources_queue, sep="")m = 0while sources_queue:print("\t\tLoop index: ", m, sep="")m += 1print("\t\t\tGetting the source by popping from the queue")print("\t\t\tSources: ", sources_queue, " ⟶ ", end="", sep="")c = sources_queue.popleft()print(sources_queue)print("\t\t\t\tSource: ", c)print("\t\t\t\tAppending to the result list: ",result, " ⟶ ", end="", sep="")result.append(c)print(result)print("\t\t\tUpdating the in-degrees of the children")print("\t\t\t\tSource: ", c, ", children: ", adj_list[c], sep="")n = 0for d in adj_list[c]:print("\t\t\t\tInner loop index: ", n)n += 1print("\t\t\t\t\tChild: ", d, sep="")print("\t\t\t\t\tDecrementing in-degree of ", d,": ", counts[d], " ⟶ ", counts[d] - 1, sep="")counts[d] -= 1if counts[d] == 0:print("\t\t\t\t\tSince in-degree of ", d," = 0, it's now a source.", sep="")print("\t\t\t\t\tAdding it to the sources queue: ",sources_queue, " ⟶ ", end="", sep="")sources_queue.append(d)print(sources_queue)# If not all letters are in result, that means there was a cycle and so# no valid ordering. Return "".if len(result) < len(counts):print("\n\tLength of the result list = ", len(result), sep="")print("\tNumber of alphabets in the alien language = ", len(counts), sep="")print("\t\tSince ", len(result), " < ", len(counts), " there's a cycle in the graph.")return ""# Otherwise, convert the ordering we found into a string and return it.return "".join(result)# Driver codedef main():words = [["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu","suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],["vanilla", "alpine", "algor", "port","norm", "nylon", "ophellia", "hidden"],["passengers", "to", "the", "unknown"],["alpha", "bravo", "charlie", "delta"],["jupyter", "ascending"]]for i in range(len(words)):print(i + 1, ".\twords = ", words[i], sep="")print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")print("-"*100)if __name__ == "__main__":main()
Just the code
Here’s the complete solution to this problem:
Solution summary
To recap, the solution to this problem can be divided into the following parts:
- Build a graph from the given words and keep track of the in-degrees of alphabets in a dictionary.
- Add the sources to a result list.
- Remove the sources and update the in-degrees of their children. If the in-degree of a child becomes 0, it’s the next source.
- Repeat until all alphabets are covered.
Time
Solution: Alien Dictionary
Statement▼
You are given a list of words written in an alien language, where the words are sorted lexicographically by the rules of this language. Surprisingly, the aliens also use English lowercase letters, but possibly in a different order.
Given a list of words written in the alien language, return a string of unique letters sorted in the lexicographical order of the alien language as derived from the list of words.
If there’s no solution, that is, no valid lexicographical ordering, you can return an empty string "".
If multiple valid orderings exist, you may return any of them.
Note: A string,
a, is considered lexicographically smaller than stringbif:
At the first position where they differ, the character in
acomes before the character inbin the alien alphabet.If one string is a prefix of the other, the shorter string is considered smaller.
Constraints:
- 1≤
words.length≤103 - 1≤
words[i].length≤20 - All characters in
words[i]are English lowercase letters.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
The naive approach is to generate all possible orders of alphabets in the alien language and then iterate over them, character by character, to select the ones that satisfy the dictionary dependencies. So, there’d be O(u!) permutations, where u is the number of unique alphabets in the alien language, and for each permutation, we’d have to check if it’s a valid partial order. That requires comparing against the dictionary words repeatedly.
This is very expensive since there are an exponential number of possible orders (u!) and only a handful of valid ones. On top of that, there’d be additional effort to compare them against the dictionary. The time complexity for this approach is O(u!). The space complexity is O(1).
Optimized approach using topological sort
We can solve this problem using the topological sort pattern. Topological sort is used to find a linear ordering of elements that have dependencies on or priority over each other. For example, if A is dependent on B or B has priority over A, then B is listed before A in topological order.
Using the list of words, we identify the relative precedence order of the letters in the words and generate a graph to represent this ordering. To traverse a graph, we can use breadth-first search to find the letters’ order.
We can essentially map this problem to a graph problem, but before exploring the exact details of the solution, there are a few things that we need to keep in mind:
-
The letters within a word don’t tell us anything about the relative order. For example, the word “educative” in the list doesn’t tell us that the letter “e” is before the letter “d.”
-
The input can contain words followed by their prefix, such as “educated” and then “educate.” These cases will never result in a valid alphabet because in a valid alphabet, prefixes are always first. We need to make sure our solution detects these cases correctly.
-
There can be more than one valid alphabet ordering. It’s fine for our algorithm to return any one of them.
-
The output dictionary must contain all unique letters within the words list, including those that could be in any position within the ordering. It shouldn’t contain any additional letters that weren’t in the input.
Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.
Step-by-step solution construction
For the graph problem, we can break this particular problem into three parts:
-
Extract the necessary information to identify the dependency rules from the words. For example, in the words [“patterns”, “interview”], the letter “p” comes before “i.”
-
With the gathered information, we can put these dependency rules into a directed graph with the letters as nodes and the dependencies (order) as the edges.
-
Lastly, we can sort the graph nodes topologically to generate the letter ordering (dictionary).
Let’s look at each part in more depth.
Part 1: Identifying the dependencies
Let’s start with example words and observe the initial ordering through simple reasoning:
["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu", "suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"]
As in the English language dictionary, where all the words starting with “a” come at the start followed by the words starting with “b,” “c,” “d,” and so on, we can expect the first letters of each word to be in alphabetical order.
["m", "m", "x", "x", "x", "x", "s", "s", "s", "s", "r", "r", "r"]
Removing the duplicates, we get the following:
["m", "x", "s", "r"]
Following the intuition explained above, we can assume that the first letters in the messages are in alphabetical order:
Looking at the letters above, we know the relative order of these letters, but we don’t know how these letters fit in with the rest of the letters. To get more information, we need to look further into our English dictionary analogy. The word “dirt” comes before “dorm.” This is because we look at the second letter when the first letter is the same. In this case, “i” comes before “o” in the alphabet.
We can apply the same logic to our alien words and look at the first two words, “mzsor” and “mqov.” As the first letter is the same in both words, we look at the second letter. The first word has “z,” and the second one has “q.” Therefore, we can safely say that “z” comes before “q” in this alien language. We now have two fragments of the letter order:
Note: Notice that we didn’t mention rules such as “m -> a”. This is fine because we can derive this relation from “m -> x”, “x -> a”.
This is it for the first part. Let’s put the pieces that we have in place.
Part 2: Representing the dependencies
We now have a set of relations mentioning the relative order of the pairs of letters:
["z -> q", "m -> x", "x -> a", "x -> v", "x -> s", "z -> x", "v -> a", "s -> r", "o -> w"]
Now the question arises, how can we put these relations together? It might be tempting to start chaining all these together. Let’s look at a few possible chains:
We can observe from our chains above that some letters might appear in more than one chain, and putting the chains into the output list one after the other won’t work. Some of the letters might be duplicated and would result in an invalid ordering. Let’s try to visualize the relations better with the help of a graph. The nodes are the letters, and an edge between two letters, “x” and “y” represents that “x” is before “y” in the alien words.
Part 3: Generating the dictionary
As we can see from the graph, four of the letters have no incoming arrows. This means that there are no letters that have to come before any of these four.
Remember: There could be multiple valid dictionaries, and if there are, then it’s fine for us to return any of them.
Therefore, a valid start to the ordering we return would be as follows:
["o", "m", "u", "z"]
We can now remove these letters and edges from the graph because any other letters that required them first will now have this requirement satisfied.
There are now three new letters on this new graph that have no in arrows. We can add these to our output list.
["o", "m", "u", "z", "x", "q", "w"]
Again, we can remove these from the graph.
Then, we add the two new letters with no in arrows.
["o", "m", "u", "z", "x", "q", "w", "v", "s"]
This leaves the following graph:
We can place the final two letters in our output list and return the ordering:
["o", "m", "u", "z", "x", "q", "w", "v", "s", "a", "r"]
Let’s now review how we can implement this approach.
Identifying the dependencies and representing them in the form of a graph is pretty straightforward. We extract the relations and insert them into an adjacency list:
Next, we need to generate the dictionary from the extracted relations: identify the letters (nodes) with no incoming links. Identifying whether a particular letter (node) has any incoming links or not from our adjacency list format can be a little complicated. A naive approach is to repeatedly iterate over the adjacency lists of all the other nodes and check whether or not they contain a link to that particular node.
This naive method would be fine for our case, but perhaps we can do it more optimally.
An alternative is to keep two adjacency lists:
- One with the same contents as the one above.
- One reversed that shows the incoming links.
This way, every time we traverse an edge, we can remove the corresponding edge from the reversed adjacency list:
What if we can do better than this? Instead of tracking the incoming links for all the letters from a particular letter, we can track the count of how many incoming edges there are. We can keep the in-degree count of all the letters along with the forward adjacency list.
In-degree corresponds to the number of incoming edges of a node.
It will look like this:
Now, we can decrement the in-degree count of a node instead of removing it from the reverse adjacency list. When the in-degree of the node reaches 0, this represents that this particular node has no incoming links left.
We perform BFS on all the letters that are reachable, that is, the in-degree count of the letters is zero. A letter is only reachable once the letters that need to be before it have been added to the output, result.
We use a queue to keep track of reachable nodes and perform BFS on them. Initially, we put the letters that have zero in-degree count. We keep adding the letters to the queue as their in-degree counts become zero.
We continue this until the queue is empty. Next, we check whether all the letters in the words have been added to the output or not. This would only happen when some letters still have some incoming edges left, which means there is a cycle. In this case, we return an empty string.
Remember: There can be letters that don’t have any incoming edges. This can result in different orderings for the same set of words, and that’s all right.
Let’s try to visualize the algorithm with the help of a set of slides below:
Delving into the actual code, the first step is to count the number of unique letters in the words and initialize the graph.
We consider adjacent words at a time and compare them character by character. Let’s call them c and d for the first and second words, respectively. If at any point they aren’t the same, we add d to the adjacency list of c. If all characters match, we check if one word is a prefix of the other. If the second word is a prefix of the first word, a topological sorting isn’t possible and we return an empty string.
from collections import defaultdict, Counter, dequedef print_string_with_markers(strn, pValue):out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]return outdef print_array_with_markers(arr, pValue):out = "["for i in range(len(arr)):if i in pValue:out += '«'out += str(arr[i]) + '»' + ", "else:out += str(arr[i]) + ", "out = out[0:len(out) - 2]out += "]"return outdef alien_order(words):# Step 0: Create data structures and find all unique letters.adj_list = defaultdict(set)# counts stores the number of unique lettersprint("\n\tGetting unique characters")counts = Counter({c: 0 for word in words for c in word})print("\t\t", counts.keys(), sep="")# Step 1: We need to populate adj_list and counts.# For each pair of adjacent words...print("\n\tComparing adjacent words")outer = 0for word1, word2 in zip(words, words[1:]):print("\t\tLoop index: ", outer, sep="")print("\t\t", print_array_with_markers(words, [outer, outer+1]), sep="")outer += 1print("\t\tWords to compare: ", word1, ", ", word2, sep="")print("\t\tIterating the words")inner = 0for c, d in zip(word1, word2):print("\t\t\tInner loop index: ", inner)print("\t\t\t\tword1: ", print_string_with_markers(word1, inner), ", c = ", c, sep="")print("\t\t\t\tword2: ", print_string_with_markers(word2, inner), ", d = ", d, sep="")inner += 1if c != d:print("\t\t\t\tThe characters are not the same")if d not in adj_list[c]:print("\t\t\t\t\tAdding '", d, "' to ", c,"'s children: ", adj_list[c], " ⟶ ", sep="", end="")adj_list[c].add(d)print(adj_list[c])print("\t\t\t\t\tIncremeting count of '",d, "' ⟶ ", sep="", end="")counts[d] += 1print(counts)breakelse:print("\t\t\t\tBoth characters are the same: '",c, "', moving to the next character", sep="")else: # Check that second word isn't a prefix of first word.if len(word2) < len(word1):return ""# Driver codedef main():words = [["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu","suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],["vanilla", "alpine", "algor", "port","norm", "nylon", "ophellia", "hidden"],["passengers", "to", "the", "unknown"],["alpha", "bravo", "charlie", "delta"],["jupyter", "ascending"]]for i in range(len(words)):print(i + 1, ".\twords = ", words[i], sep="")print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")print("-"*100)if __name__ == "__main__":main()
The next step is to find all sources, that is, vertices with in-degree =0. These nodes are the first ones to be removed from our graph and added to the result list.
We remove the source and decrease the in-degree of its children by 1. If a child’s in-degree becomes 0, it becomes the new source. We repeat this step until all vertices have been visited and added to the result list.
from collections import defaultdict, Counter, dequedef print_string_with_markers(strn, pValue):out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]return outdef print_array_with_markers(arr, pValue):out = "["for i in range(len(arr)):if i in pValue:out += '«'out += str(arr[i]) + '»' + ", "else:out += str(arr[i]) + ", "out = out[0:len(out) - 2]out += "]"return outdef alien_order(words):# Step 0: Create data structures and find all unique letters.adj_list = defaultdict(set)# counts stores the number of unique lettersprint("\n\tGetting unique characters")counts = Counter({c: 0 for word in words for c in word})print("\t\t", counts.keys(), sep="")# Step 1: We need to populate adj_list and counts.# For each pair of adjacent words...print("\n\tComparing adjacent words")outer = 0for word1, word2 in zip(words, words[1:]):print("\t\tLoop index: ", outer, sep="")print("\t\t", print_array_with_markers(words, [outer, outer+1]), sep="")outer += 1print("\t\tWords to compare: ", word1, ", ", word2, sep="")print("\t\tIterating the words")inner = 0for c, d in zip(word1, word2):print("\t\t\tInner loop index: ", inner)print("\t\t\t\tword1: ", print_string_with_markers(word1, inner), ", c = ", c, sep="")print("\t\t\t\tword2: ", print_string_with_markers(word2, inner), ", d = ", d, sep="")inner += 1if c != d:print("\t\t\t\tThe characters are not the same")if d not in adj_list[c]:print("\t\t\t\t\tAdding '", d, "' to ", c,"'s children: ", adj_list[c], " ⟶ ", sep="", end="")adj_list[c].add(d)print(adj_list[c])print("\t\t\t\t\tIncremeting count of '",d, "' ⟶ ", sep="", end="")counts[d] += 1print(counts)breakelse:print("\t\t\t\tBoth characters are the same: '",c, "', moving to the next character", sep="")else: # Check that second word isn't a prefix of first word.if len(word2) < len(word1):return ""# Step 2: We need to repeatedly pick off nodes with an indegree of 0.result = []sources_queue = deque([c for c in counts if counts[c] == 0])print("\n\tRemoving the sources")print("\t\tSources: ", sources_queue, sep="")m = 0while sources_queue:print("\t\tLoop index: ", m, sep="")m += 1print("\t\t\tGetting the source by popping from the queue")print("\t\t\tSources: ", sources_queue, " ⟶ ", end="", sep="")c = sources_queue.popleft()print(sources_queue)print("\t\t\t\tSource: ", c)print("\t\t\t\tAppending to the result list: ",result, " ⟶ ", end="", sep="")result.append(c)print(result)print("\t\t\tUpdating the in-degrees of the children")print("\t\t\t\tSource: ", c, ", children: ", adj_list[c], sep="")n = 0for d in adj_list[c]:print("\t\t\t\tInner loop index: ", n)n += 1print("\t\t\t\t\tChild: ", d, sep="")print("\t\t\t\t\tDecrementing in-degree of ", d,": ", counts[d], " ⟶ ", counts[d] - 1, sep="")counts[d] -= 1if counts[d] == 0:print("\t\t\t\t\tSince in-degree of ", d," = 0, it's now a source.", sep="")print("\t\t\t\t\tAdding it to the sources queue: ",sources_queue, " ⟶ ", end="", sep="")sources_queue.append(d)print(sources_queue)# Driver codedef main():words = [["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu","suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],["vanilla", "alpine", "algor", "port","norm", "nylon", "ophellia", "hidden"],["passengers", "to", "the", "unknown"],["alpha", "bravo", "charlie", "delta"],["jupyter", "ascending"]]for i in range(len(words)):print(i + 1, ".\twords = ", words[i], sep="")print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")print("-"*100)if __name__ == "__main__":main()
Now, our algorithm runs as expected and returns an ordering of the alphabet in the alien language. However, it doesn’t cater to a cycle in the word order. Therefore, we add a conditional statement that checks if all the letters are in the result list. If not, we have a cycle.
from collections import defaultdict, Counter, dequedef print_string_with_markers(strn, pValue):out = strn[:pValue] + '«' + strn[pValue] + '»' + strn[pValue+1:]return outdef print_array_with_markers(arr, pValue):out = "["for i in range(len(arr)):if i in pValue:out += '«'out += str(arr[i]) + '»' + ", "else:out += str(arr[i]) + ", "out = out[0:len(out) - 2]out += "]"return outdef alien_order(words):# Step 0: Create data structures and find all unique letters.adj_list = defaultdict(set)print()# counts stores the number of unique lettersprint("\n\tGetting unique characters")counts = Counter({c: 0 for word in words for c in word})print("\t\t", counts.keys(), sep="")# Step 1: We need to populate adj_list and counts.# For each pair of adjacent words...print("\n\tComparing adjacent words")outer = 0for word1, word2 in zip(words, words[1:]):print("\t\tLoop index: ", outer, sep="")print("\t\t", print_array_with_markers(words, [outer, outer+1]), sep="")outer += 1print("\t\tWords to compare: ", word1, ", ", word2, sep="")print("\t\tIterating the words")inner = 0for c, d in zip(word1, word2):print("\t\t\tInner loop index: ", inner)print("\t\t\t\tword1: ", print_string_with_markers(word1, inner), ", c = ", c, sep="")print("\t\t\t\tword2: ", print_string_with_markers(word2, inner), ", d = ", d, sep="")inner += 1if c != d:print("\t\t\t\tThe characters are not the same")if d not in adj_list[c]:# print("\t\t\t\t\tAdding '", d, "' to ", c, "'s children: ", adj_list[c], " ⟶ ", sep="", end="")adj_list[c].add(d)print(adj_list[c])print("\t\t\t\t\tIncremeting count of '",d, "' ⟶ ", sep="", end="")counts[d] += 1print(counts)breakelse:print("\t\t\t\tBoth characters are the same: '",c, "', moving to the next character", sep="")else: # Check that second word isn't a prefix of first word.if len(word2) < len(word1):return ""# Step 2: We need to repeatedly pick off nodes with an indegree of 0.result = []sources_queue = deque([c for c in counts if counts[c] == 0])print("\n\tRemoving the sources")print("\t\tSources: ", sources_queue, sep="")m = 0while sources_queue:print("\t\tLoop index: ", m, sep="")m += 1print("\t\t\tGetting the source by popping from the queue")print("\t\t\tSources: ", sources_queue, " ⟶ ", end="", sep="")c = sources_queue.popleft()print(sources_queue)print("\t\t\t\tSource: ", c)print("\t\t\t\tAppending to the result list: ",result, " ⟶ ", end="", sep="")result.append(c)print(result)print("\t\t\tUpdating the in-degrees of the children")print("\t\t\t\tSource: ", c, ", children: ", adj_list[c], sep="")n = 0for d in adj_list[c]:print("\t\t\t\tInner loop index: ", n)n += 1print("\t\t\t\t\tChild: ", d, sep="")print("\t\t\t\t\tDecrementing in-degree of ", d,": ", counts[d], " ⟶ ", counts[d] - 1, sep="")counts[d] -= 1if counts[d] == 0:print("\t\t\t\t\tSince in-degree of ", d," = 0, it's now a source.", sep="")print("\t\t\t\t\tAdding it to the sources queue: ",sources_queue, " ⟶ ", end="", sep="")sources_queue.append(d)print(sources_queue)# If not all letters are in result, that means there was a cycle and so# no valid ordering. Return "".if len(result) < len(counts):print("\n\tLength of the result list = ", len(result), sep="")print("\tNumber of alphabets in the alien language = ", len(counts), sep="")print("\t\tSince ", len(result), " < ", len(counts), " there's a cycle in the graph.")return ""# Otherwise, convert the ordering we found into a string and return it.return "".join(result)# Driver codedef main():words = [["mzosr", "mqov", "xxsvq", "xazv", "xazau", "xaqu","suvzu", "suvxq", "suam", "suax", "rom", "rwx", "rwv"],["vanilla", "alpine", "algor", "port","norm", "nylon", "ophellia", "hidden"],["passengers", "to", "the", "unknown"],["alpha", "bravo", "charlie", "delta"],["jupyter", "ascending"]]for i in range(len(words)):print(i + 1, ".\twords = ", words[i], sep="")print("\tDictionary = \"", alien_order(words[i]), "\"", sep="")print("-"*100)if __name__ == "__main__":main()
Just the code
Here’s the complete solution to this problem:
Solution summary
To recap, the solution to this problem can be divided into the following parts:
- Build a graph from the given words and keep track of the in-degrees of alphabets in a dictionary.
- Add the sources to a result list.
- Remove the sources and update the in-degrees of their children. If the in-degree of a child becomes 0, it’s the next source.
- Repeat until all alphabets are covered.