LeetCode(269) -- Alien Dictionary

Problem

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"

Solution

BFS:

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, List<Character>> adjList = new HashMap<>();
        Map<Character, Integer> count = new HashMap<>();
        for (String word : words) {
            for (Character c : word.toCharArray()) {
                adjList.put(c, new ArrayList<>());
                count.put(c, 0);
            }
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return "";
            }
            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                if (word1.charAt(j) != word2.charAt(j)) {
                    adjList.get(word1.charAt(j)).add(word2.charAt(j));
                    count.put(word2.charAt(j), count.get(word2.charAt(j)) + 1);
                    break;
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        for (Character c : count.keySet()) {
            if (count.get(c) == 0) {
                queue.add(c);
            }
        }
        while (!queue.isEmpty()) {
            Character c = queue.remove();
            sb.append(c);
            for (Character next : adjList.get(c)) {
                count.put(next, count.get(next) - 1);
                if (count.get(next) == 0) {
                    queue.add(next);
                }
            }
        }
        
        if (sb.length() < count.size()) {
            return "";
        }
        return sb.toString();
    }
}

DFS:

下面的dfs这个方法中，seen如果包含某个key, 并且是false,代表这个节点访问过，但它还有子节点没访问，标记为灰色。如果包含某个key，并且是true，说明它已经完全访问过了，标记为黑色。

class Solution {
    private Map<Character, List<Character>> adjList = new HashMap<>();
    private Map<Character, Boolean> seen = new HashMap<>();
    private StringBuilder output = new StringBuilder();

    public String alienOrder(String[] words) {
        for (String word : words) {
            for (Character c : word.toCharArray()) {
                adjList.putIfAbsent(c, new ArrayList<>());
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            if (word1.length() > word2.length() && word1.startsWith(word2)) {
                return "";
            }

            for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
                if (word1.charAt(j) != word2.charAt(j)) {
                    adjList.get(word2.charAt(j)).add(word1.charAt(j));
                    break;
                }
            }
        }

        for (Character c : adjList.keySet()) {
            boolean result = dfs(c);
            if (!result) return "";
        }

        if (output.length() < adjList.size()) {
            return "";
        }
        return output.toString();
    }

    private boolean dfs(Character c) {
        if (seen.containsKey(c)) {
            return seen.get(c);
        }
        seen.put(c, false);
        for (Character next : adjList.get(c)) {
            boolean result = dfs(next);
            if (!result) return false;
        }
        seen.put(c, true);
        output.append(c);
        return true;
    }
}