269. Alien Dictionary

becuse this Q is about order, use topology sort

be careful this case

exception case is : 
for ex: 
ab
a.  => return ""

if (s1.length() > s2.length() && s2.equals(s1.substring(0, s2.length()))) {
    return "";
}

and duplicate path should not add to map, and indgree

Set<Character> set = map.getOrDefault(s[j], new HashSet<>());
if (!set.contains(t[j])) {
    set.add(t[j]);
    map.put(s[j], set);
    indegree.put(t[j], indegree.getOrDefault(t[j], 0)+1);
}

T: O(V+E), V is number of char , E is edge
S: O(V)

class Solution {
    public String alienOrder(String[] words) {
        int n = words.length;
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        
        // 這裡要先把 char 都建立過, 不然之後會取不到, 之後只有建入度不為 0 的部分
        for (String word : words) {
            for (char c : word.toCharArray()) {
                indegree.put(c, 0);
            }
        }
        
        for (int i = 0; i < n-1; i++) {
            String s1 = words[i];
            String s2 = words[i+1];
            if (s1.length() > s2.length() && s2.equals(s1.substring(0, s2.length()))) {
                return "";
            }
            char[] s = words[i].toCharArray();
            char[] t = words[i+1].toCharArray();
            for (int j = 0; j < Math.min(s.length, t.length); j++) {
                if (s[j] == t[j]) {
                    continue;
                }
                Set<Character> set = map.getOrDefault(s[j], new HashSet<>());
                if (!set.contains(t[j])) {
                    set.add(t[j]);
                    map.put(s[j], set);
                    indegree.put(t[j], indegree.getOrDefault(t[j], 0)+1);
                }
                break;
            }
        }
        
        Queue<Character> queue = new LinkedList<>();
        for (char key : indegree.keySet()) {
            if (indegree.get(key) == 0) {
                queue.offer(key);
            }
        }
        
        StringBuilder res = new StringBuilder();
        while (!queue.isEmpty()) {
            char cur = queue.poll();
            res.append(cur);
            
            for (char next : map.getOrDefault(cur, new HashSet<>())) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        return res.length() == indegree.size() ? res.toString() : "";
            
    }
}

/*
wrt
wrf
er
ett
rftt

t < f
w < e
r < t
e < r

w - e - r - t - f


topology sort

1. build graph
this is a words list
so use Map<char, list<char>>
indegree<char, int>

1.a
for (int i = 0; i < words.length -1; i++) {
    String s = 
    String t = 
    
exception case is : s.length() > t.length && t.equals(s.substring(0, t.length)), 
for ex: 
ab
a.  => return ""

1.b
then compare s , t, add to map, but notice, if s->t is duplicate, dont add!

2. topology sort algo

3. result.size() != count of char return ""
or return result

T: O(V+E), V is number of char , E is edge
S: O(V)

*/

沒有判斷 s -> t 是否存在重複的話, 這個 case 會不過

Set<Character> set = graph.get(w1[j]);
if (!set.contains(w2[j])) {
    set.add(w2[j]);

最後還要檢查 res 長度是不是跟 indegree 長度一樣, 不然這 test case fail

return res.length() == indegree.size() ? res.toString() : "";