Question

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.

Solution

  • Method 1: Topological sort 
     class Solution {
      public String alienOrder(String[] words) {
          Map<Character, Set<Character>> adj = new HashMap<>();
          Map<Character, Integer> indegree = new HashMap<>();
          for(String word: words){
              for(char c : word.toCharArray()){
                  indegree.put(c, 0);
              }
          }
          for(int i = 1; i < words.length; i++){
              int maxLen = Math.min(words[i].length(), words[i - 1].length());
              char[] arr1 = words[i - 1].toCharArray(), arr2 = words[i].toCharArray();
              for(int j = 0; j < maxLen; j++){
                  if(arr1[j] != arr2[j]){
                      Set<Character> set = adj.containsKey(arr1[j]) ? adj.get(arr1[j]): new HashSet<>();
                      if(!set.contains(arr2[j])){
                          set.add(arr2[j]);
                          adj.put(arr1[j], set);
                          indegree.put(arr2[j], indegree.get(arr2[j]) + 1);
                      }
                      break;
                  }
              }
          }
          Queue<Character> q = new LinkedList<>();
          for(Character c : indegree.keySet()){
              if(indegree.get(c) == 0) q.offer(c);
          }
          StringBuilder result = new StringBuilder();
          while(!q.isEmpty()){
              char c = q.poll();
              result.append(c);
              if(adj.get(c) == null) continue;
              for(Character neigh: adj.get(c)){
                  indegree.put(neigh, indegree.get(neigh) - 1);
                  if(indegree.get(neigh) == 0) q.offer(neigh);
              }
          }
          for(int count: indegree.values()){
              if(count > 0) return "";
          }
          return result.toString();
      }
  }