269.Alien-Dictionary

269. Alien Dictionary

题目地址

https://leetcode.com/problems/alien-dictionary/

题目描述

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.

代码

Approach #1 Topology Traversal + BFS

class Solution {
  public String alienOrder(String[] words) {
    if (words == null || words.length == 0) return "";

    Map<Character, Set<Character>> map = new HashMap<>();
    Map<Character, Integer> degree = new HashMap<>();
    for (String s: words){
        for (char c: s.toCharArray()) {
          map.putIfAbsent(c, new HashSet());
          degree.putIfAbsent(c, 0);
      }
    }

    for (int i = 0; i < words.length - 1; i++) {
      String cur = words[i];
      String next = words[i + 1];
      for (int j = 0; j < Math.min(cur.length(), next.length()); j++) {
        char c1 = cur.charAt(j);
        char c2 = next.charAt(j);
        if (c1 != c2) {
          Set<Character> set = map.get(c1);
          if (!set.contains(c2)) {    // ESSENTIAL！！
            set.add(c2);
            map.put(c1, set);
            degree.put(c2, degree.get(c2) + 1);
          }
          break;
        }
      }
    }

    // BFS
    Queue<Character> q = new LinkedList<Character>();
    for (char c : degree.keySet()) {
      if (degree.get(c) == 0) {
        q.add(c);
      }
    }

    StringBuffer sb = new StringBuffer();
    while (!q.isEmpty()) {
      char c = q.poll();
      sb.append(c);
      if (map.containsKey(c)) {
        for (char c2 : map.get(c)) {
          degree.put(c2, degree.get(c2) - 1);
          if (degree.get(c2) == 0) {
            q.offer(c2);
          }
        }
      }
    }

    if (sb.length() != degree.size()) return "";
    return sb.toString();
  }
}

Approach #2 DFS

DFS, mark visited. When dfs down to an leaf element, it'll be the last element of the final output. (reverse order)

class Solution {
    Map<Character, List<Character>> map = new HashMap<>();
    Map<Character,Integer> visited = new HashMap<>();
    StringBuffer sb = new StringBuffer();

    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) return "";

        // build graph, and visited map
        buildGraph(words);

        // Topological sort with dfs
        for (char c : map.keySet()) {
            if (!dfs(c)) {
                return "";
            }
        }

        return sb.toString();
    }

    private void buildGraph(String[] words) {
        for (String word : words) {
            for (char c : word.toCharArray()) {
                if (!map.containsKey(c)) {
                    map.put(c, new ArrayList<>());
                    visited.put(c, 0);
                }
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            int index = 0;
            while (index < words[i].length() && index < words[i + 1].length()) {
                char c1 = words[i].charAt(index);
                char c2 = words[i + 1].charAt(index);
                if (c1 != c2) {
                    map.get(c1).add(c2);
                    break;
                }
                index++;
            }
        }
    }

    // Traverse all the way to the leaves in topological order
    private boolean dfs(Character c) {
        if (visited.get(c) == 1)    return true;    // can reach the leaves
        if (visited.get(c) == -1)    return false; // Do not go back

        visited.put(c, -1);
        for (char neightbor : map.get(c)) {
            if (!dfs(neightbor)) { // False is returned on repeated elements
                return false;
            }
        }

        visited.put(c, 1);
        sb.insert(0, c);  // leaf element, add to buffer
        return true;
    }

}