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 words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example, Given the following words in dictionary,

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

The correct order is: "wertf".

There are few points not clear :

• each word itself has no order, ie abc can not deduce the order of a, b ,c
• if any chars has not found and there is no dependence what then ?

public class Solution {
    public String alienOrder(String[] words) {
        if(words == null || words.length == 0) return "";

        Map<Character, List<Character>> map = new HashMap<>();

        Set<Character> letters = new HashSet<>();
        for(String s : words){
            for(char c : s.toCharArray()){
                letters.add(c);
            }
        }

        int[] indg = new int[26];

        for(int i=1; i< words.length; i++){
            String prev = words[i-1];
            String cur = words[i];
            for(int k=0; k< prev.length() && k < cur.length(); k++){
                Character c1 = prev.charAt(k) ;
                Character c2 = cur.charAt(k);

                if(c1 != c2){
                    if(!map.containsKey(c1)){
                        List<Character> list = new ArrayList<>();
                        map.put(c1, list);
                    }
                    map.get(c1).add(c2);
                    indg[c2-'a']++;
                    break;
                }
            }
        }
        PriorityQueue<Character> pq = new PriorityQueue<>();

        for(Character c : letters){
            if(indg[c-'a'] == 0) pq.offer(c);
        }

        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            Character c = pq.poll();
            sb.append(c);
            List<Character> list = map.get(c);
            if(list == null) continue;
            for(Character ch : list){
                if(--indg[ch-'a'] == 0) pq.offer(ch);
            }
        }

        return sb.length() == letters.size() ? sb.toString(): "";


    }
}

Solution. Topological sort.

1. find all possible edges, which means, in two adjecent strings, s1, s2, if s1[i] != s2[j], there is an edge from s1[i] to s2[j];
2. in the mean time, build a in-degree map to reflect the fact that how many nodes points to current node, also need to mantain a list of node a current can reach.

public class Solution {
    public String alienOrder(String[] words) {
        if(words == null || words.length == 0) return "";

        Map<Character, List<Character>> map = new HashMap<>();

        Set<Character> letters = new HashSet<>();
        for(String s : words){
            for(char c : s.toCharArray()){
                letters.add(c);
            }
        }

        int[] indg = new int[26];

        for(int i=1; i< words.length; i++){
            String prev = words[i-1];
            String cur = words[i];
            for(int k=0; k< prev.length() && k < cur.length(); k++){
                Character c1 = prev.charAt(k) ;
                Character c2 = cur.charAt(k);

                if(c1 != c2){
                    if(!map.containsKey(c1)){
                        List<Character> list = new ArrayList<>();
                        map.put(c1, list);
                    }
                    map.get(c1).add(c2);
                    indg[c2-'a']++;
                    break;
                }
            }
        }
        PriorityQueue<Character> pq = new PriorityQueue<>();

        for(Character c : letters){
            if(indg[c-'a'] == 0) pq.offer(c);
        }

        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            Character c = pq.poll();
            sb.append(c);
            List<Character> list = map.get(c);
            if(list == null) continue;
            for(Character ch : list){
                if(--indg[ch-'a'] == 0) pq.offer(ch);
            }
        }

        return sb.length() == letters.size() ? sb.toString(): "";


    }
}

the below solution is not very clear. ```java public class Solution { public String alienOrder(String[] words) { Map> graph = new HashMap<>(); StringBuilder sb = new StringBuilder(); for(int i =0; i< words.length; i++){ String s = words[i]; for(int j=0; j()); } }

        if(i >0){
            buildEdge(graph, words[i-1], s);
        }
    }

    Map<Character, Integer> visited = new HashMap<>(); //(-1, node visited, 1 node neighbors visited)
    Iterator it = graph.entrySet().iterator();
    while(it.hasNext()){
        Map.Entry pair = (Map.Entry)it.next();
        char ch = (char)pair.getKey();
        if(!tSort(ch, graph, sb, visited)){
            return "";
        }
    }

    return sb.toString();
}
void buildEdge(Map<Character, Set<Character>> graph, String prev, String cur){
    if(prev == null || cur == null){
        return;
    }
    for(int i=0; i< prev.length() && i< cur.length(); i++){
        char p = prev.charAt(i);
        char q = cur.charAt(i);
        if(p != q){
            if(!graph.get(p).contains(q)){
                graph.get(p).add(q);
            }
            break;
        }
    }
}

boolean tSort(char ch, Map<Character, Set<Character>> graph, StringBuilder sb, Map<Character,Integer> visited){
    if(visited.containsKey(ch)){
        if(visited.get(ch) == -1){
            return false;
        }else{
            return true;
    }
    }else{
        visited.put(ch, -1);
    }

    Set<Character> neighbors = graph.get(ch);
    for(char n : neighbors){
        if(!tSort(n, graph, sb, visited)){
            return false;
        }
    }
    sb.insert(0, ch);
    visited.put(ch, 1);
    return true;
}

}

updating in-degrees, failed at ["za","zb","ca","cb"] test cases why(output is "azc")?

```java
public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> ingrees = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for(int i =0; i< words.length; i++){
            String s = words[i];
            for(int j=0; j<s.length(); j++){
                if(!graph.containsKey(s.charAt(j))){
                    graph.put(s.charAt(j), new HashSet<Character>());
                    if(!ingrees.containsKey(s.charAt(j)))
                        ingrees.put(s.charAt(j), 0);
                }
            }

            if(i >0){
                updateIngrees(graph, ingrees, words[i-1], s);
            }else{
                if(words[0].length() > 0 ){
                    ingrees.put(words[0].charAt(0), 0);
                }
            }
        }

        Queue<Character> queue = new LinkedList<>();

        Iterator it = ingrees.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry pair = (Map.Entry)it.next();
            char ch = (char)pair.getKey();
            int val = (int)pair.getValue();
            if(val == 0){
                queue.offer(ch);
            }
        }

        while(!queue.isEmpty()){
            char top = queue.poll();
            sb.append(top);
            Set<Character> neighbors = graph.get(top);
            for(char n : neighbors){
                ingrees.put(n, ingrees.get(n)-1);
                if(ingrees.get(n) == 0){
                  queue.offer(n);  
                } 
            }
        }

        String res = sb.toString();
        if(res.length() == graph.size()) return res;
        else return "";
    }

    void updateIngrees(Map<Character, Set<Character>> graph, Map<Character, Integer> ingrees, String prev, String cur){
        if(prev == null || cur == null) return;
        for(int i=0; i< prev.length() && i< cur.length(); i++){
            char p = prev.charAt(i);
            char q = cur.charAt(i);
            if(p != q){
                //update edges
                if(!graph.containsKey(p)){
                    Set<Character> set = new HashSet<>();
                    set.add(q);
                    graph.put(p, set);
                }else{
                    graph.get(p).add(q);
                }
                // update ingrees;
                if(!ingrees.containsKey(p)){
                    ingrees.put(p, 0);
                }

                if(ingrees.containsKey(q)){
                    ingrees.put(q, ingrees.get(q) +1);// this line is actually failing the code, you can simply increase ingree on q, cause if you have mutiple <p-q> instances while building, the q's ingree is not properly calculated.
                }else{
                    ingrees.put(q, 1);
                }
                break;
            }
        }
    }


}