269. Alien Dictionary

/ * 269. Alien Dictionary

 * There is a new alien language that uses the English alphabet. However, the order among letters are unknown to you.

 * You are given a list of strings words from the dictionary, where words are sorted lexicographically by the rules of this new language.

 * Derive the order of letters in this language, and return it. If the given input is invalid, return “”. If there are multiple valid solutions, return any of them.

 * Example 1:

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

 * Output: “wertf”

 * Example 2:

 * Input: words = [“z”,”x”]

 * Output: “zx”

 */

See solution to the problem at github here:

https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/hard/AlienDictionary.java

You have to pay attention to the words in question where it states “where words are sorted lexicographically by the rules of this new language”. This means that words are lexicographically sorted based on some rule. Then the question asks to return the list of characters back based on the lexicographic dependencies specified in the words.

This translates to figuring out the dependency order of character, which can be found via topological sort. See more about topological sort on wikipedia here: https://en.wikipedia.org/wiki/Topological_sorting.

The algorithm thus is based on these steps:

  1. Create a dependency order of characters.
  2. Traverse the unique characters via running a topsort per character.
  3. Top sort is simply running dfs on characters by traversing dependencies until you reach a character with no dependency.
    1. During recursion skip characters already visited.
    2. If you run into a cycle (identified via the visiting variable below), then the dependency order can’t be identified.

Here is the code:

public String alienOrder(String[] words) {
        int numWords = words.length;
        Map<Character, String> wordDependencies = new HashMap<>();
        Set<Character> uniqueChars = new HashSet<>();
        //create a unique list of chars
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                uniqueChars.add(word.charAt(i));
            }
        }
        //create a dependency map
        for (int i = 1; i < numWords; i++) {
            String wordA = words[i - 1];
            String wordB = words[i];
            int inLen = Math.min(wordA.length(), wordB.length());
            int index = 0;
            while (index < inLen && wordA.charAt(index) == wordB.charAt(index)) {
                index++;
            }
            if (index < inLen) {
                String strDep = wordDependencies.getOrDefault(wordA.charAt(index), "");
                strDep = strDep + wordB.charAt(index);
                wordDependencies.put(wordA.charAt(index), strDep);
            }
        }
        StringBuilder builder = new StringBuilder();
        Set<Character> visited = new HashSet<>();
        //iterate through the unique chars while like running toposort to process dependencies
        for (Character ch : uniqueChars) {
            if (!visited.contains(ch)) {
                Set<Character> visiting = new HashSet<>();
                int val = topoSort(wordDependencies, builder, visited, ch, visiting);
                if (val != 0) {
                    return "";
                }
            }
        }
        return builder.reverse().toString();
    }

    /**
     * process the char dependencies via running toposort
     * @param wordDependencies
     * @param builder
     * @param visited
     * @param ch
     * @param visiting
     * @return
     */
    int topoSort(Map<Character, String> wordDependencies, StringBuilder builder, Set<Character> visited,
                 Character ch, Set<Character> visiting) {
        visiting.add(ch);
        String dep = wordDependencies.get(ch);
        if (null != dep) {
            for (int i = 0; i < dep.length(); i++) {
                Character depCh = dep.charAt(i);
                if (visiting.contains(depCh)) {
                    return -1;
                } else if (!visited.contains(depCh)) {
                    int val = topoSort(wordDependencies, builder, visited, depCh, visiting);
                    if (val != 0) {
                        return val;
                    }
                }
            }
        }
        visiting.remove(ch);
        visited.add(ch);
        builder.append(ch);
        return 0;
    }