Find lexical order of alphabets from a given dictionary of words - PrismoSkills
Problem: Given a dictionary of words, find the order of alphabets that make that dictionary.
Solution:
Dictionary is a sorted data-structure.
So if we traverse the first alphabets of each word in the dictionary, we will get lexical order for some of alphabets.
This order of alphabets will be lexicographically sorted, but it may have some holes in it.
For example: In the above case, first letters only contain the alphabets 2 and a.
This can be resolved by looking at the second level of alphabets.
But there is a catch.
The second level of alphabets can be matched only if first level of alphabets is same.
For example, in the above, we can only compare second level of alphabets in 2ad with 2bd but we cannot compare second level of alphabets in 2bd with abb
Once all these comparisons are done level-wise, we can create a map which will store immediate lower-level characters per alphabet.
Then we simply traverse this map for each character and wherever the length of the path becomes equal to number of alphabets, we get a solution.
Example: For the above dictionary : {"2ad", "2bd", "abb", "abd"},
Problem: Given a dictionary of words, find the order of alphabets that make that dictionary.
Solution:
Dictionary is a sorted data-structure.
So if we traverse the first alphabets of each word in the dictionary, we will get lexical order for some of alphabets.
This order of alphabets will be lexicographically sorted, but it may have some holes in it.
For example: In the above case, first letters only contain the alphabets 2 and a.
This can be resolved by looking at the second level of alphabets.
But there is a catch.
The second level of alphabets can be matched only if first level of alphabets is same.
For example, in the above, we can only compare second level of alphabets in 2ad with 2bd but we cannot compare second level of alphabets in 2bd with abb
Once all these comparisons are done level-wise, we can create a map which will store immediate lower-level characters per alphabet.
Then we simply traverse this map for each character and wherever the length of the path becomes equal to number of alphabets, we get a solution.
Example: For the above dictionary : {"2ad", "2bd", "abb", "abd"},
- We build a map of characters as:
chars coming after 2: [a] (by seeing first char of "2bd" and "abb")
chars coming after a: [b] (by seeing second char of "2ad" and "2bd")
chars coming after b: [d] (by seeing third char of "abb", "abd") - We traverse this map.
Since order of hash-map is not guaranteed, let's say we first got 'a'
Following 'a' through the map, the order we get is 'a', 'b', 'd' which is less than number of characters 4
So, we ditch 'a' and go to the next char in the map until the length of ordered set obtained becomes 4 - If we use a LinkedHashSet and LinkedHashMap, this order can be obtained much earlier.
