Java Topological,


  • 0
    T

    The regular topological sorting. Need to notice some corner cases :
    "abc", "abcd" => "abcd"
    "abcd", "abc" => ""
    If meet a different character, this different will determine the order. However, if all chars are the same when reaching the end of the shortest word, the short length ahead is valid. Because in dictionary, the shortest one will always appear first.
    So add a isDiff flag to check this case.

        public String alienOrder(String[] words) {
            if (words == null || words.length == 0) {
                return "";
            }
            HashMap<Character, Set<Character>> map = new HashMap<>();
            Set<Character> set = new HashSet<Character>();
            int[] indegree = new int[26];
            for (String word : words) {
                for (int i = 0; i < word.length(); i++) {
                    set.add(word.charAt(i));
                }
            }
            for (int i = 1; i < words.length; i++) {
                String pre = words[i - 1];
                String cur = words[i];
                int len = Math.min(pre.length(), cur.length());
                boolean isDiff = true;
                for (int j = 0; j < len; j++) {
                    char c1 = pre.charAt(j);
                    char c2 = cur.charAt(j);
                    if (c1 == c2) {
                        isDiff = false;
                        continue;
                    }
                    if (!map.containsKey(c1)) {
                        map.put(c1, new HashSet<Character>());
                    }
                    if (!map.get(c1).contains(c2)) {
                        map.get(c1).add(c2);
                        indegree[c2 - 'a']++;
                    }
                    isDiff = true;
                    break;
                }
                if (!isDiff && pre.length() > cur.length()) {
                    return "";
                }
            }
            Queue<Character> queue = new LinkedList<>();
            for (char c : set) {
                if (indegree[c - 'a'] == 0) {
                    queue.offer(c);
                }
            }
            StringBuilder builder = new StringBuilder();
            while (!queue.isEmpty()) {
                char c = queue.poll();
                builder.append(c);
                if (map.containsKey(c)) {
                    for (char character : map.get(c)) {
                        indegree[character - 'a']--;
                        if (indegree[character - 'a'] == 0) {
                            queue.offer(character);
                        }
                    }
                }
    
            }
            return builder.length() == set.size() ? builder.toString() : "";
        }
    

Log in to reply
 

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