269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]


Output: "wertf"

Example 2:

Input:

[
  "z",
  "x"
]


Output: "zx"

Example 3:

Input:

[
  "z",
  "x",
  "z"
] 


Output:""
Explanation: The order is invalid, so return "".

Note:

1. You may assume all letters are in lowercase.

2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.

3. If the order is invalid, return an empty string.

4. There may be multiple valid order of letters, return any one of them is fine.

Thoughts:

1. BFS: construct the relative ordering between characters by observing the first difference of the character from the two consecutive inputs-> Then construct the relative ordering using BFS (with queue)

2. DFS: Check whether there is a cycle in the graph when building the return answer.

   1. state = -1, not exist

   2. 0: Exist. Non-visited.

   3. 1: Visiting

   4. 2: Visited

3. Topological Sort:

Code: BFS

class Solution {
    public String alienOrder(String[] words) {
        Map <Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
        Map <Character, Integer> level = new HashMap <Character, Integer>();
        for(String word : words)
            for (char c : word.toCharArray())
                level.put(c, 0);

        // find the dependency by pairwise comparason
        for(int i = 0; i < words.length - 1; i++){
            String cur = words[i];
            String next = words[i + 1];
            int len = Math.min(cur.length(), next.length());

            // search for char difference to find the relative order
            for (int j = 0; j < len; j++){
                char c1 = cur.charAt(j);
                char c2 = next.charAt(j);
                if(c1 != c2){
                    // put the order into the map
                    Set<Character> set = map.getOrDefault(c1, new HashSet<Character>());
                    if(!set.contains(c2)){
                        set.add(c2);
                        map.put(c1, set);
                        // increasing the processing priority
                        level.put(c2, level.get(c2) + 1);
                    }
                    break;
                }
            }
        }

        // BFS
        Queue<Character> q = new LinkedList<Character>();
        for(char c: level.keySet()) 
            if (level.get(c) == 0) q.add(c);

        String res = "";
        while(!q.isEmpty()){
            char c = q.remove();
            res += c;
            // propagate the dependency, increase its neighbors' priority
            if(map.containsKey(c)){
                for(char succ: map.get(c)){
                    level.put(succ, level.get(succ) - 1);
                    if (level.get(succ) == 0) q.add(succ);
                }
            }
        }
        // check whether all dependency has been meet: all the priority in level has become 0
        if(res.length() != level.size()) return "";
        return res;

    }
}

Code: DFS

class Solution {
    private final int N = 26;
    public String alienOrder(String[] words) {
        boolean [][] adj = new boolean [N][N];
        int [] visited = new int [N];
        StringBuilder sb = new StringBuilder();
        buildGraph(words, adj, visited);
        for(int i = 0 ; i < N; i++){
            if(visited[i]==0){ // unvisited
                if(!dfs(adj,visited,sb, i)) return "";
            }
        }

        return sb.reverse().toString();
    }

    private boolean dfs( boolean [][] adj, int[] visited, StringBuilder sb, int i){
        visited[i] = 1; // mark as visiting
        // checking its neightbor 
        for(int j = 0; j < N; j++){
            if(adj[i][j]){
                if(visited[j] == 1) return false; // cycle detection
                if (visited[j] == 0){ // only visit unvisited nodes that are "larger" in the ordering
                    if(!dfs(adj, visited, sb, j)) return false;
                }
            }
        }

        visited[i] = 2; // mark as visited
        sb.append((char)(i + 'a'));
        return true;
    }

    private void buildGraph(String[] words, boolean[][] adj, int[] visited){
        Arrays.fill(visited, -1);
        for(int i = 0; i < words.length; i++){
            for(char c: words[i].toCharArray()) visited[c-'a'] = 0;
            if(i > 0){
                String w1 = words[i - 1], w2 = words[i];
                int len = Math.min(w1.length(), w2.length());
                for(int j = 0; j < len; j++){
                    char c1 = w1.charAt(j), c2 = w2.charAt(j);
                    if(c1 != c2){
                        // imposing the ordering
                        adj[c1 - 'a'][c2 - 'a'] = true;
                        break;
                    }
                }
            }
        }
    }
}

Code: Topological Sort

  class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        # build the graph using greater and less default dict
        smaller = collections.defaultdict(set)
        larger = collections.defaultdict(set)

        for i in range(len(words) - 1):
            minlen = min(len(words[i]), len(words[i + 1]))
            j = 0 
            while j < minlen and words[i][j] == words[i + 1][j]:
                j += 1

            if j < minlen:
                smaller[words[i][j]].add(words[i + 1][j])
                larger[words[i + 1][j]].add(words[i][j])

        # adding free chars
        charset = set(''.join(words))
        res = []

        deque = collections.deque([x for x in charset if x not in larger])

        while deque:
            i = deque.popleft()
            if i in smaller:
                for j in smaller[i]:
                    larger[j].remove(i)
                    if len(larger[j]) == 0:
                        del larger[j]
                        # add into the queue
                        deque.append(j)
            res.append(i)

        # check whether there is still ordering constraints 
        if len(larger) > 0: return ""
        else: return "".join(res)