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

冷不防 2023-07-03 10:59 68阅读 0赞

### [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.

#### 第一次做;巩固一下拓扑排序, 这里也可以说是拓扑遍历; 相似的题:两道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<Character>()).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() : "";
            
        }
    }

#### [力扣优秀题解][Link 1] ####

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();
    
        }
    }

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/alien-dictionary/solution/java-tuo-bu-pai-xu-by-zxy0917/