Leetcode 269 题BFS方法有一个test case有问题

哈喽大家，今天刷到269 Alien Dictionary 的时候， 用的BFS 方法，但是发现有个test case很奇怪，["ba", "bc"], 跑下来结果是"abc", 但是理想答案应该是"bac" 才对啊， 希望有明白的同学能给解答解答！！

1. class Solution {
   
2.     public String alienOrder(String[] words) {
   
3.         int[] degree = new int[26];
   
4.         int count = 0;
   
5.         StringBuilder res = new StringBuilder();
   
6.         
   
7.         for (String word : words) {
   
8.             for (char c : word.toCharArray()) {
   
9.                 if (degree[c - 'a'] == 0) {
   
10.                     degree[c - 'a'] = 1;
    
11.                     count++;
    
12.                 }
    
13.             }
    
14.         }
    
15.         
    
16.         HashMap<Character, Set<Character>> map = new HashMap<>();
    
17.         
    
18.         for (int i = 0; i < words.length - 1; i++) {
    
19.             int len = Math.min(words[i].length(), words[i + 1].length());
    
20.             for (int j = 0; j < len; j++) {
    
21.                 char cur = words[i].charAt(j);
    
22.                 char next = words[i + 1].charAt(j);
    
23.                 if (cur != next) {
    
24.                     if (!map.containsKey(cur)) {
    
25.                         map.put(cur, new HashSet<>());
    
26.                     }
    
27.                     if (map.get(cur).add(next)) {
    
28.                         degree[next - 'a']++;
    
29.                     }
    
30.                     break;
    
31.                 }
    
32.                 if (j == words[i + 1].length() - 1 && words[i + 1].length() < words[i].length()) {
    
33.                     return "";
    
34.                 }
    
35.             }
    
36.         }
    
37.         
    
38.         Queue<Character> queue = new LinkedList<>();
    
39.         for (int i = 0; i < 26; i++) {
    
40.             if (degree[i] == 1) {
    
41.                 queue.offer((char)(i + 'a'));
    
42.             }
    
43.         }
    
44.         
    
45.         while (!queue.isEmpty()) {
    
46.             Character c = queue.poll();
    
47.             res.append(c);
    
48.             if (map.containsKey(c)) {
    
49.                 for (char ch : map.get(c)) {
    
50.                     if (--degree[ch - 'a'] == 1) {
    
51.                         queue.offer(ch);
    
52.                     }
    
53.                 }
    
54.             }
    
55.         }
    
56.         
    
57.         if (res.length() != count) return "";
    
58.         
    
59.         return res.toString();
    
60.     }
    
61. }

复制代码

premium题 锁了看不了..

一剑终情 发表于 2020-11-3 03:10
premium题 锁了看不了..

不好意思啊， 我把题目要求贴上去了

题目要求在此字数字数字数

题目只代表a在c前面，b在任何位置都可以

如果test case错了你可以给Leetcode举报，他们采纳的话会给你发coin