Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/269.html
There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.
You are given a list of strings words
from the alien language's dictionary, where the strings in words
are sorted lexicographically by the rules of this new language.
Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return ""
. If there are multiple solutions, return any of them.
Example 1:
Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"
Example 2:
Input: words = ["z","x"] Output: "zx"
Example 3:
Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return ""
.
Constraints:
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i]
consists of only lowercase English letters.
Algorithm
It is actually a problem of directed graph traversal
.
The solution consists of two steps:
- Create the graph and indegree map:
- For each character in the words, initialize its indegree to 0.
- For each adjacent pair of words, find the first character that is different.
- If the second character is not already in the adjacency list of the first character, add it and increment its indegree by 1.
- Stop processing the current pair of words and move on to the next pair.
- If all characters of the first word match the second word and the first word is longer than the second, it means that the order of characters is invalid, so return an empty string.
- Topological sort
- Add all characters with an indegree of 0 to the queue.
- For each character in the queue, add it to the result and decrement the indegree of its neighbors.
- If the indegree of a neighbor becomes 0, add it to the queue.
- If the length of the result equals the length of the indegree map, return the result as a string. Otherwise, return an empty string.
Code
-
import java.util.*; public class Alien_Dictionary { public static void main(String[] args) { Alien_Dictionary out = new Alien_Dictionary(); Solution s = out.new Solution(); Solution_bfs s2 = out.new Solution_bfs(); String[] words = new String[] { "wrt", "wrf", "er", "ett", "rftt" }; System.out.println(s.alienOrder(words)); System.out.println(s2.alienOrder(words)); } // ref: http://buttercola.blogspot.com/2015/09/leetcode-alien-dictionary.html public class Solution_bfs { /** * @param words: a list of words * @return: a string which is correct order */ public String alienOrder(String[] words) { // Write your code here if (words == null || words.length == 0) { return ""; } // step 1: construct the graph // Map<Character, List<Character>> adjMap = new HashMap<>(); constructGraph(words, adjMap); int numNodes = adjMap.size(); StringBuilder result = new StringBuilder(); // toplogical sorting // Map<Character, Integer> indegreeMap = new HashMap<>(); for (Character node : adjMap.keySet()) { indegreeMap.put(node, 0); } for (Character node : adjMap.keySet()) { for (Character neighbor : adjMap.get(node)) { int indegree = indegreeMap.get(neighbor); indegree += 1; indegreeMap.put(neighbor, indegree); } } // start from indegree=0 Queue<Character> queue = new PriorityQueue<>(); for (Character node : indegreeMap.keySet()) { if (indegreeMap.get(node) == 0) { // starting node, can only be one, cannot be 2 starting with 0 indegree queue.offer(node); } } while (!queue.isEmpty()) { char curNode = queue.poll(); result.append(curNode); for (char neighbor : adjMap.get(curNode)) { int indegree = indegreeMap.get(neighbor); indegree -= 1; indegreeMap.put(neighbor, indegree); // @note: key is here. // for A->B, B->C, A-C: C will not be counted until its indgree is 0 if (indegree == 0) { queue.offer(neighbor); } } } if (result.length() < numNodes) { return ""; } return result.toString(); } private void constructGraph(String[] words, Map<Character, List<Character>> adjMap) { // construct nodes for (String word : words) { for (Character c : word.toCharArray()) { adjMap.put(c, new ArrayList<>()); // c to all its next } } // construct edges for (int i = 1; i < words.length; i++) { String prev = words[i - 1]; String curr = words[i]; for (int j = 0; j < prev.length() && j < curr.length(); j++) { if (prev.charAt(j) != curr.charAt(j)) { adjMap.get(prev.charAt(j)).add(curr.charAt(j)); break; } } } } } public class Solution { // dfs public String alienOrder(String[] words) { // Step 1: build the graph Map<Character, Set<Character>> graph = new HashMap<>(); for (int i = 0; i < words.length; i++) { String currentWord = words[i]; for (int j = 0; j < currentWord.length(); j++) { if (!graph.containsKey(currentWord.charAt(j))) { graph.put(currentWord.charAt(j), new HashSet<>()); } } if (i > 0) { connectGraph(graph, words[i - 1], currentWord); } } // Step 2: topological sorting StringBuffer sb = new StringBuffer(); Map<Character, Integer> visited = new HashMap<Character, Integer>(); // mark as visited: visited.put(vertexId, -1); for (Map.Entry<Character, Set<Character>> entry: graph.entrySet()) { char vertexId = entry.getKey(); if (!topologicalSort(vertexId, graph, sb, visited)) { return ""; } } return sb.toString(); } private void connectGraph(Map<Character, Set<Character>> graph, String prev, String curr) { if (prev == null || curr == null) { return; } int len = Math.min(prev.length(), curr.length()); for (int i = 0; i < len; i++) { char p = prev.charAt(i); char q = curr.charAt(i); if (p != q) { // so if same duplicated work, will not reach here and not update graph if (!graph.get(p).contains(q)) { graph.get(p).add(q); } break; } } } private boolean topologicalSort( char vertexId, Map<Character, Set<Character>> graph, StringBuffer sb, Map<Character, Integer> visited ) { if (visited.containsKey(vertexId)) { // visited if (visited.get(vertexId) == -1) { // -1 meaning visited, cycle found return false; } // already in the list if (visited.get(vertexId) == 1) { return true; } } visited.put(vertexId, -1); // mark as visited Set<Character> neighbors = graph.get(vertexId); for (char neighbor : neighbors) { if (!topologicalSort(neighbor, graph, sb, visited)) { return false; } } sb.insert(0, vertexId); visited.put(vertexId, 1); // restore visited return true; } } } ############ class Solution { public String alienOrder(String[] words) { boolean[][] g = new boolean[26][26]; boolean[] s = new boolean[26]; int cnt = 0; int n = words.length; for (int i = 0; i < n - 1; ++i) { for (char c : words[i].toCharArray()) { if (cnt == 26) { break; } c -= 'a'; if (!s[c]) { ++cnt; s[c] = true; } } int m = words[i].length(); for (int j = 0; j < m; ++j) { if (j >= words[i + 1].length()) { return ""; } char c1 = words[i].charAt(j), c2 = words[i + 1].charAt(j); if (c1 == c2) { continue; } if (g[c2 - 'a'][c1 - 'a']) { return ""; } g[c1 - 'a'][c2 - 'a'] = true; break; } } for (char c : words[n - 1].toCharArray()) { if (cnt == 26) { break; } c -= 'a'; if (!s[c]) { ++cnt; s[c] = true; } } int[] indegree = new int[26]; for (int i = 0; i < 26; ++i) { for (int j = 0; j < 26; ++j) { if (i != j && s[i] && s[j] && g[i][j]) { ++indegree[j]; } } } Deque<Integer> q = new LinkedList<>(); for (int i = 0; i < 26; ++i) { if (s[i] && indegree[i] == 0) { q.offerLast(i); } } StringBuilder ans = new StringBuilder(); while (!q.isEmpty()) { int t = q.pollFirst(); ans.append((char) (t + 'a')); for (int i = 0; i < 26; ++i) { if (i != t && s[i] && g[t][i]) { if (--indegree[i] == 0) { q.offerLast(i); } } } } return ans.length() < cnt ? "" : ans.toString(); } }
-
// OJ: https://leetcode.com/problems/alien-dictionary/ // Time: O(N) // Space: O(1) class Solution { public: string alienOrder(vector<string>& A) { unordered_map<int, unordered_set<int>> G; int indegree[26] = {}; for (auto &s : A) { for (char c : s) G[c - 'a'] = {}; } for (int i = 1; i < A.size(); ++i) { int j = 0; for (; j < min(A[i - 1].size(), A[i].size()); ++j) { if (A[i - 1][j] == A[i][j]) continue; G[A[i - 1][j] - 'a'].insert(A[i][j] - 'a'); break; } if (j == A[i].size() && j < A[i - 1].size()) return ""; } for (auto &[from, tos] : G) { for (int to : tos) { indegree[to]++; } } queue<int> q; for (int i = 0; i < 26; ++i) { if (G.count(i) && indegree[i] == 0) q.push(i); } string ans; while (q.size()) { int u = q.front(); q.pop(); ans += u + 'a'; for (int v : G[u]) { if (--indegree[v] == 0) q.push(v); } } return ans.size() == G.size() ? ans : ""; } };
-
''' >>> a = ['a','b','c'] >>> zip(a, a[1:]) [('a', 'b'), ('b', 'c')] # same as pairwise() >>> from itertools import pairwise >>> pairwise(a) <itertools.pairwise object at 0x108458730> >>> list(pairwise(a)) [('a', 'b'), ('b', 'c')] ''' from collections import defaultdict, deque class Solution: def alienOrder(self, words: List[str]) -> str: graph = defaultdict(set) indegree = defaultdict(int) 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: indegree[c] = 0 # necessary for final char counting 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[v] += 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 = collections.deque() q = deque([c for c in indegree if indegree[c] == 0]) while q: u = q.pop() result += u for v in graph[u]: inDegree[v] -= 1 if inDegree[v] == 0: q.append(v) # Words = ['z', 'x', 'y', 'x'] return result if len(result) == len(indegree) else '' ############ import collections class Node(object): def __init__(self, val): self.val = val self.neighbors = [] def connect(self, node): self.neighbors.append(node) def getNbrs(self): return self.neighbors class Solution(object): def alienOrder(self, words): """ :type words: List[str] :rtype: str """ def dfs(root, graph, visited): visited[root] = 1 for nbr in graph[root].getNbrs(): if visited[nbr.val] == 0: if not dfs(nbr.val, graph, visited): return False elif visited[nbr.val] == 1: return False visited[root] = 2 self.ans += root return True self.ans = "" graph = {} visited = collections.defaultdict(int) self.topNum = 0 for i in range(0, len(words) - 1): a = words[i] b = words[i + 1] i = 0 while i < len(a) and i < len(b): if a[i] != b[i]: nodeA = nodeB = None if a[i] not in graph: nodeA = Node(a[i]) graph[a[i]] = nodeA else: nodeA = graph[a[i]] if b[i] not in graph: nodeB = Node(b[i]) graph[b[i]] = nodeB else: nodeB = graph[b[i]] nodeA.connect(nodeB) break i += 1 if i < len(a) and i >= len(b): return "" for c in graph: if visited[c] == 0: if not dfs(c, graph, visited): return "" unUsedSet = set() for word in words: for c in word: unUsedSet.add(c) for c in unUsedSet: if c not in graph: self.ans += c return self.ans[::-1]