LeetCode Top Interview Questions 269. Alien Dictionary(Java版;Hard)

welcome to my blog
LeetCode Top Interview Questions 269. Alien Dictionary(Java版;Hard)
タイトルの説明

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:

You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

初めてやるトポロジーのソートを強固にすると、ここでもトポロジー遍歴と言える.似たような問題:2つのCourse Schedule II 210問題とCourse Schedule 207問題

/*
    ,  BFS?


          :
1.    ;             
2.    ;              
3.      0      ;     LinkedList
4.          ;         ;                         ,       


  1: BFS,     
  2:       ,             
  3:        ,                   
  4:          ,           
  5:   sb        count,        ;       


  :   map   
  :          char.   queue.add((char)('a'+i));
*/
class Solution {
    public String alienOrder(String[] words) {
        //      ,   a   b,  key a, value b
        HashMap<Character, Set<Character>>map = new HashMap<>();
        int n = words.length;
        //        ;   :                
        for(int i=0; i<n-1; i++){
            //  :                  
            for(int j=0; j<words[i].length() && j<words[i+1].length(); j++){
                //          ,       
                char ch1 = words[i].charAt(j), ch2 = words[i+1].charAt(j);
                if(ch1 == ch2)
                    continue;
                //  ...
                // map.getOrDefault(ch1, new HashSet()).add(ch2); //      
                Set<Character> set = map.getOrDefault(ch1, new HashSet<Character>());
                set.add(ch2);
                map.put(ch1, set); //     map.put()
                //     ?       :   :["za","zb","ca","cb"]   "abzc";        ""
                break;
            }
        }
        
        //         
        int[] inDegree = new int[26];
        //-1        
        Arrays.fill(inDegree, -1);
        //          0
        for(String word : words){
            for(char ch : word.toCharArray()){
                inDegree[ch-'a'] = 0;
            }
        }
        
        //  :          ;        
        int count = 0;
        for(int i=0; i<26; i++){
            if(inDegree[i]==0)
                count++;
        }
        
        //  map       
        for(Character ch : map.keySet()){
            for(Character c : map.get(ch)){
                inDegree[c-'a']++;
            }
        }
        //         0   
        LinkedList<Character> queue = new LinkedList<>();
        for(int i=0; i<26; i++)
            if(inDegree[i]==0)
                //  ,          char
                queue.add((char)('a'+i));
        
        //        
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()){
            Character ch = queue.poll();
            //         sb
            sb.append(ch);
            //  ch         
            if(map.containsKey(ch)){
                for(Character c : map.get(ch)){
                    inDegree[c-'a']--;
                    if(inDegree[c-'a']==0)
                        queue.add(c);
                }
            }
        }
        //  sb        count,        ;       
        return sb.length()==count? sb.toString() : "";
        
    }
}

優秀な問題解を力で締める.

class Solution {
    public String alienOrder(String[] words) {
        //1.   
        Map<Character, Set<Character>> map = new HashMap<>();
        for (int i = 0; i < words.length - 1; i++) {
            for (int j = 0; j < words[i].length() && j < words[i + 1].length(); j++) {
                //      ，     
                if (words[i].charAt(j) == words[i + 1].charAt(j)) continue;
                //            
                Set<Character> set = map.getOrDefault(words[i].charAt(j), new HashSet<>());
                set.add(words[i + 1].charAt(j));
                map.put(words[i].charAt(j), set);
                break;
            }
        }

        //2.    
        //         
        int[] degrees = new int[26];
        Arrays.fill(degrees, -1);
        //  ，  26    words   ，          ：          -1，             
        for (String str : words) {
            //             0
            for (char c : str.toCharArray())
                degrees[c - 'a'] = 0;
        }
        for (char key : map.keySet()) {
            for (char val : map.get(key)) {
                degrees[val - 'a']++;
            }
        }
        //  StringBuilder      
        StringBuilder sb = new StringBuilder();
        //    Queue     0   
        Queue<Character> list = new LinkedList<>();

        int count = 0;//       
        for (int i = 0; i < 26; i++) {
            if (degrees[i] != -1) count++;
            if (degrees[i] == 0) {
                list.add((char) ('a' + i));
            }
        }

        while (!list.isEmpty()) {
            Character cur = list.poll();
            sb.append(cur);
            //      -1
            if (map.containsKey(cur)) {
                Set<Character> set = map.get(cur);
                for (Character c : set) {
                    degrees[c - 'a']--;
                    if (degrees[c - 'a'] == 0) list.add(c);
                }
            }
        }

        //      
        if (sb.length() != count) return "";
        else return sb.toString();

    }
}