0269. Alien Dictionary
https://leetcode.com/problems/alien-dictionary
Description
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.
A string s
is lexicographically smaller than a string t
if at the first letter where they differ, the letter in s
comes before the letter in t
in the alien language. If the first min(s.length, t.length)
letters are the same, then s
is smaller if and only if s.length < t.length
.
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.
ac
How to intepret as a topological problem?
How to build the graph?
class Solution {
public String alienOrder(String[] words) {
// edge cases
if (words == null || words.length == 0)
return "";
// map is more robust than array
Map<Character, Integer> inde = new HashMap<Character, Integer>();
Map<Character, Set<Character>> g = new HashMap<Character, Set<Character>>();
// get chars
for (String w : words) {
for (int i = 0; i < w.length(); i++) {
char c = w.charAt(i);
inde.put(c, 1);
if(!g.containsKey(c)) g.put(c, new HashSet<Character>());
}
}
// build graph, get indegree
for (int i = 0; i < words.length - 1; i++) {
char[] f = words[i].toCharArray();
char[] s = words[i+1].toCharArray();
int len = Math.min(f.length, s.length);
for (int j = 0; j < len; j++) {
if (f[j] == s[j]) continue;
if (g.get(f[j]).add(s[j])) { // ignore duplicate edge
inde.put(s[j], inde.get(s[j]) + 1);
}
break;
}
}
// BFS
StringBuilder res = new StringBuilder();
Queue<Character> q = new LinkedList<Character>();
for (char c : inde.keySet()){
if (inde.get(c) == 1) q.offer(c);
}
while (!q.isEmpty()) {
char c = q.poll();
res.append(c);
for (char next : g.get(c)) {
inde.put(next, inde.get(next) - 1);
if (inde.get(next) == 1) q.offer(next);
}
}
// validate
if (res.length() != inde.size()) {
return "";
} else {
return res.toString();
}
}
}
/*
build a graph
indegree
BFS
*/
Last updated
Was this helpful?