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.
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.
public String alienOrder(String[] words){ if (words == null || words.length == 0) { return""; } Map<Character, List<Character>> graph = new HashMap<>(); Map<Character, Integer> indegree = new HashMap<>(); buildGraph(words, graph, indegree); Queue<Character> queue = new LinkedList<>(); // push all 0-indegree nodes for (char v : graph.keySet()) { if (indegree.get(v) == 0) { queue.offer(v); } } int count = graph.size(); // number of nodes in total StringBuilder sb = new StringBuilder(); while (queue.size() > 0) { char v = queue.poll(); sb.append(v); --count; List<Character> neighborList = graph.get(v); // for each neighbor w for (char w : neighborList) { int degree = indegree.get(w); indegree.put(w, degree - 1); if (degree - 1 == 0) { queue.offer(w); } } } if (count == 0) return sb.toString(); elsereturn""; }
privatevoidbuildGraph(String[] words, Map<Character, List<Character>> graph, Map<Character, Integer> indegree){ // setup all possible nodes for (int i = 0; i < words.length; ++i) { for (int j = 0; j < words[i].length(); ++j) { char ch = words[i].charAt(j); graph.put(ch, graph.getOrDefault(ch, new ArrayList<>())); indegree.put(ch, 0); } } // add edges and calculate indegrees for (int i = 0; i < words.length - 1; ++i) { String s1 = words[i]; String s2 = words[i + 1]; int j = 0; while (j < s1.length() && j < s2.length() && s1.charAt(j) == s2.charAt(j)) { ++j; } // consider: "abc" vs. "abcd", "abc" vs. "abc", "abcd" vs. "abc" -> no info. gained if (j < s1.length() && j < s2.length()) { char c1 = s1.charAt(j); char c2 = s2.charAt(j); if (graph.get(c1).contains(c2) == false) { // do not add duplicate edges graph.get(c1).add(c2); indegree.put(c2, indegree.getOrDefault(c2, 0) + 1); // indegree } } } }
Time: $O(NK + V + E)$ where $N$ is the size of words and $K$ is the average length of each word. Space: $O(V)$