269. Alien Dictionary

• Time: $O(26 + |\texttt{words}| - 1)$
• Space: $O(26 + |\texttt{words}| - 1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 class Solution { public: string alienOrder(vector& words) { unordered_map> graph; vector inDegree(26); buildGraph(graph, words, inDegree); return topology(graph, inDegree); } private: void buildGraph(unordered_map>& graph, const vector& words, vector& inDegree) { // create node for each character in each word for (const string& word : words) for (const char c : word) if (!graph.count(c)) graph[c] = unordered_set(); for (int i = 1; i < words.size(); ++i) { const string& first = words[i - 1]; const string& second = words[i]; const int length = min(first.length(), second.length()); for (int j = 0; j < length; ++j) { const char u = first[j]; const char v = second[j]; if (u != v) { if (!graph[u].count(v)) { graph[u].insert(v); ++inDegree[v - 'a']; } break; // later characters' order are meaningless } // first = "ab", second = "a" -> invalid if (j == length - 1 && first.length() > second.length()) { graph.clear(); return; } } } } string topology(unordered_map>& graph, vector& inDegree) { string s; queue q; for (const auto& [c, _] : graph) if (inDegree[c - 'a'] == 0) q.push(c); while (!q.empty()) { const char u = q.front(); q.pop(); s += u; for (const char v : graph[u]) if (--inDegree[v - 'a'] == 0) q.push(v); } // words = ["z", "x", "y", "x"] return s.length() == graph.size() ? s : ""; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 class Solution { public String alienOrder(String[] words) { Map> graph = new HashMap<>(); int[] inDegree = new int[26]; buildGraph(graph, words, inDegree); return topology(graph, inDegree); } private void buildGraph(Map> graph, String[] words, int[] inDegree) { // create node for each character in each word for (final String word : words) for (final char c : word.toCharArray()) graph.putIfAbsent(c, new HashSet<>()); for (int i = 1; i < words.length; ++i) { final String first = words[i - 1]; final String second = words[i]; final int length = Math.min(first.length(), second.length()); for (int j = 0; j < length; ++j) { final char u = first.charAt(j); final char v = second.charAt(j); if (u != v) { if (!graph.get(u).contains(v)) { graph.get(u).add(v); ++inDegree[v - 'a']; } break; // later characters' order are meaningless } // first = "ab", second = "a" -> invalid if (j == length - 1 && first.length() > second.length()) { graph.clear(); return; } } } } private String topology(Map> graph, int[] inDegree) { StringBuilder sb = new StringBuilder(); Queue q = graph.keySet() .stream() .filter(c -> inDegree[c - 'a'] == 0) .collect(Collectors.toCollection(ArrayDeque::new)); while (!q.isEmpty()) { final char u = q.poll(); sb.append(u); for (final char v : graph.get(u)) if (--inDegree[v - 'a'] == 0) q.offer(v); } // words = ["z", "x", "y", "x"] return sb.length() == graph.size() ? sb.toString() : ""; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution: def alienOrder(self, words: List[str]) -> str: graph = {} inDegree = [0] * 26 self._buildGraph(graph, words, inDegree) return self._topology(graph, inDegree) def _buildGraph(self, graph: Dict[chr, Set[chr]], words: List[str], inDegree: List[int]) -> None: # create node for each character in each word for word in words: for c in word: if c not in graph: graph[c] = set() for first, second in zip(words, words[1:]): length = min(len(first), len(second)) for j in range(length): u = first[j] v = second[j] if u != v: if v not in graph[u]: graph[u].add(v) inDegree[ord(v) - ord('a')] += 1 break # later characters' order are meaningless # first = 'ab', second = 'a' . invalid if j == length - 1 and len(first) > len(second): graph.clear() return def _topology(self, graph: Dict[chr, Set[chr]], inDegree: List[int]) -> str: s = '' q = deque() for c in graph: if inDegree[ord(c) - ord('a')] == 0: q.append(c) while q: u = q.pop() s += u for v in graph[u]: inDegree[ord(v) - ord('a')] -= 1 if inDegree[ord(v) - ord('a')] == 0: q.append(v) # words = ['z', 'x', 'y', 'x'] return s if len(s) == len(graph) else ''