Alien Dictionary 269

Description

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 words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example, Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Note: You may assume all letters are in lowercase. If the order is invalid, return an empty string. There may be multiple valid order of letters, return any one of them is fine.

Hint

topological sort

some points about what is 'lexicographical order'. I copy Java String.compareTo() method for reference:

Java.lang.String @Contract(pure=true) public int compareTo(@org.jetbrains.annotations.NotNull String anotherString) Compares two strings lexicographically. The comparison is based on the Unicode value of each character in the strings. The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true. This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value: this.charAt(k)-anotherString.charAt(k)

If there is no index position at which they differ, then the shorter string lexicographically precedes the longer string. In this case, compareTo returns the difference of the lengths of the strings -- that is, the value: this.length()-anotherString.length()

Method

one : BFS + graph (build graph with degree using BFS) two : DFS

Time & Space

Code

one :

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()){
                     degree.put(c, 0);
                }
           }

           for (int i = 0; i < words.length - 1; i++){
                String cur = words[i];
                String next = words[i + 1];

                int idx1 = 0;
                int idx2 = 0;
                while (idx1 < cur.length() && idx2 < next.length()){
                       char tmp1 = cur.charAt(idx1);
                       char tmp2 = next.charAt(idx2);
                     if (tmp1 != tmp2){
                         if (!map.containsKey(tmp1)){
                              map.put(tmp1, new HashSet<Character>());
                         }
                         if (!map.get(tmp1).contains(tmp2)){
                         map.get(tmp1).add(tmp2);
                         degree.put(tmp2, degree.get(tmp2) + 1);
                         }
                         break;
                     }
                     idx1++;
                     idx2++;
                }
                if (cur.length() > next.length() && idx2 == next.length()){
                    return "";
                }
           }

                Queue<Character> q = new LinkedList<Character>();
                StringBuilder sb = new StringBuilder();
                for (char c : degree.keySet()){
                     if (degree.get(c) == 0){
                         q.offer(c);
                     }
                }

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

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

    }

two :

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

            boolean[][] graph = new boolean[26][26];
            int[] visited = new int[26];
            Arrays.fill(visited, -1);
            StringBuilder sb = new StringBuilder();


            for (int i = 0; i < words.length; i++){
                  for (char c : words[i].toCharArray()){
                       visited[c - 'a'] = 0;
                  }
                  if (i > 0){
                      String cur = words[i - 1];
                      String next = words[i];
                      int idx1 = 0;
                      int idx2 = 0;
                      while (idx1 < cur.length() && idx2 < next.length()){
                          char c1 = cur.charAt(idx1);
                          char c2 = next.charAt(idx2);
                           if (c1 != c2){
                               graph[c1 - 'a'][c2 - 'a'] = true;
                               break;
                           }
                           idx1++;
                           idx2++;
                      }
                      if (cur.length() > next.length() && idx2 == next.length()){
                          return "";
                      }
                  }
             }


            for (int i = 0; i < 26; i++){
                 if (visited[i] == 0){
                     if (!dfs(graph, visited, i, sb)){
                         return "";
                     }
                 }
            }
            return sb.reverse().toString();

     }

     private boolean dfs(boolean[][] graph, int[] visited, int i, StringBuilder sb){
             visited[i] = 1;
             for (int j = 0; j < 26; j++){
                  if (graph[i][j]){
                       if (visited[j] == 1) {
                           return false;
                       }
                       if (visited[j] == 0){
                           if (!dfs(graph, visited, j, sb)){
                                return false;
                           }
                       }
                  }
             }
             visited[i] = 2;
             sb.append((char) (i + 'a'));
             return true;
     }


}