Update with the corner case ["wrtkj","wrt"]


  • 0

    Re: Java AC solution using BFS

    As leetcode add one more test case, the old version won't pass.

    The solution is to compare the length of previous String and current String 's length, if the counter j reach cur.length() while pre.length() > cur.length(), then it is a corner case like ["abcde", "abc"]

    My solution as follow:

    public class Solution {
        public String alienOrder(String[] words) {
            if (words == null || words.length == 0) {return "";}
            HashMap<Character, Set<Character>> graph = new HashMap<>();
            HashSet<Character> set = new HashSet<Character>();
            
            for (String s: words) {
                for (int i = 0; i < s.length(); i++) {set.add(s.charAt(i));}
            }
            
            int[] inDegree = new int[26];
            for (int i = 1; i < words.length; i++) {
                String pre = words[i - 1], cur = words[i];
                int j = 0;
                for (j = 0; j < Math.min(pre.length(), cur.length()); j++) {
                    char preC = pre.charAt(j), curC = cur.charAt(j);
                    if (preC != curC) {
                        if (!graph.containsKey(preC)) {graph.put(preC, new HashSet<Character>());}
                        if (!graph.get(preC).contains(curC)) {inDegree[curC - 'a']++;}
                        graph.get(preC).add(curC);
                        break;
                    }
                }
                // which is really important to handle the corner case ["abcde", "abc"]
                if (j == Math.min(pre.length(), cur.length()) && pre.length() > cur.length()) {return "";}
            }
            
            LinkedList<Character> queue = new LinkedList<Character>();
            for (int i = 0; i < inDegree.length; i++) {
                if (inDegree[i] == 0) {
                    char c = (char) ('a' + i);
                    if (set.contains(c)) {queue.offer(c);}
                }
            }
            
            StringBuilder sb = new StringBuilder();
            while (!queue.isEmpty()) {
                char c = queue.poll();
                System.out.println(c);
                sb.append(c);
                if (graph.containsKey(c)) {
                    for (char d : graph.get(c)) {
                        inDegree[d - 'a']--;
                        if (inDegree[d - 'a'] == 0) {queue.offer(d);}
                    }
                }
            }
            
            return sb.length() == set.size() ? sb.toString() : "";
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.