269. Alien Dictionary
There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.
You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.
Lexicographically Smaller
A string
ais lexicographically smaller than a stringbif in the first position whereaandbdiffer, stringahas a letter that appears earlier in the alien language than the corresponding letter inb. If the firstmin(a.length, b.length)characters do not differ, then the shorter string is the lexicographically smaller one.
If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".
Otherwise, 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 are multiple solutions, return any of them.
Example 1:
Example 2:
Example 3:
Solution:
DFS
class Solution {
public String alienOrder(String[] words) {
Map<Character, List<Character>> graph = new HashMap<>();
for (String word : words){
for (char c : word.toCharArray()){
graph.putIfAbsent(c, new ArrayList<>());
}
}
for (int i = 0; i < words.length - 1; i++){
String word1 = words[i];
String word2 = words[i + 1];
if (word1.length() > word2.length() && word1.startsWith(word2)){
return "";
}
for (int j = 0; j < Math.min(word1.length(), word2.length()); j++){
if (word1.charAt(j) != word2.charAt(j)){
graph.get(word1.charAt(j)).add(word2.charAt(j));
break;
}
}
}
Map<Character, Boolean> seen = new HashMap<>();
StringBuilder output = new StringBuilder();
for (Character c : graph.keySet()){
boolean result = dfs(c, graph, seen, output);
if (result == true){
return "";
}
}
return output.reverse().toString();
}
private boolean dfs(Character c, Map<Character, List<Character>> graph, Map<Character, Boolean> seen, StringBuilder output){
if (seen.containsKey(c)){
return seen.get(c);
}
seen.put(c, true);
for (Character next : graph.get(c)){
boolean result = dfs(next, graph, seen, output);
if (result == true){
return true;
}
}
seen.put(c, false);
output.append(c);
return false;
}
}
class Solution {
private Map<Character, List<Character>> reverseAdList = new HashMap<>();
private Map<Character, Boolean> seen = new HashMap<>();
private StringBuilder output = new StringBuilder();
public String alienOrder(String[] words) {
for (String word : words){
for (char c : word.toCharArray()){
reverseAdList.putIfAbsent(c, new ArrayList<>());
}
}
for (int i = 0; i < words.length - 1; i++){
String word1 = words[i];
String word2 = words[i+1];
if (word1.length() > word2.length() && word1.startsWith(word2)){
return "";
}
for (int j = 0; j < Math.min(word1.length(), word2.length()); j++){
if (word1.charAt(j) != word2.charAt(j)){
reverseAdList.get(word1.charAt(j)).add(word2.charAt(j));
break;
}
}
}
for (Character c: reverseAdList.keySet()){
boolean result = dfs(c); // check 是否有回路
if (result == true){// 有回路
return "";
}
}
return output.reverse().toString();
}
private boolean dfs(Character c){
if (seen.containsKey(c)){
return seen.get(c);
}
seen.put(c, true);
for (Character next : reverseAdList.get(c)){
boolean result = dfs(next);
if (result == true){
return true;
}
}
seen.put(c, false);
output.append(c);
return false;
}
}
看不懂题系列 => 好像看懂了点儿 题目大概意思是 需要找到外星人的 语言单词 它也是由26个字母组成, 但是与人类的顺序规则不同. 需要你按照题目中的规定 将人类的单词根据一定规律, 翻译成外形人的单词, 如果input的提供的单词不符合规定, 返回"".
Lexicographically Smaller
A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alien language than the corresponding letter in b. If the first min(a.length, b.length) characters do not differ, then the shorter string is the lexicographically smaller one.
[apple, banna] : 'a' < 'b' ✅
[apple, ape] : ap p ? ap e => 'e' < 'p' => the correct order [ape, apple]
Input: words = ["wrt","wrf","er","ett","rftt"]
The input is already sorted
[ape, apes] ✅ [apes, ape] ❌
wrt
wrf
er
ett
rftt
wrt vs wrf: => 't' < 'f' in alien
wrf vs er : => 'w' < 'e' in alien
er vs ett : => 'r' < 't' in alien => 'r' < 'f' < 't'
ett vs rftt : => 'e' < 'r' in alien => 'e' <'r' < 'f' < 't' => 'w' < 'e' < 'r' < 'f' < 't'
DFS 用来查看是否有cycle, 有cycle 则不符合
=> 看代码理解
class Solution {
private Map<Character, List<Character>> reverseAdjList = new HashMap<>();
private Map<Character, Boolean> seen = new HashMap<>();
private StringBuilder output = new StringBuilder();
public String alienOrder(String[] words) {
// Step 0: Put all unique letters into reverseAdjList as keys.
for (String word : words){
for (char c : word.toCharArray()){
reverseAdjList.putIfAbsent(c, new ArrayList<>());
// putIfAbsent 是Java中Map接口的一个方法
// 其作用是仅当指定的键尚未与某个值关联时, 才将键映射到给定的值
// 如果该键已经有一个值, 那么该方法不会替换现有的值, 而是保留原来的值
}
}
// w []
// e []
// r []
// t []
// f []
// Step 1: Find all edges and add reverse edges to reverseAdjList.
for (int i = 0; i < words.length - 1; i++){
String word1 = words[i]; // wrt
String word2 = words[i+1]; // wrf
// Check the word2 is not a prefix of word1
if (word1.length() > word2.length() && word1.startsWith(word2)){
return ""; // wrt wrf ✅
// wrtx wrt ❌
}
// Find the first non match and insert the corresponding relation.
for (int j = 0; j < Math.min(word1.length(), word2.length()); j++){
if (word1.charAt(j) != word2.charAt(j)){
reverseAdjList.get(word2.charAt(j)).add(word1.charAt(j));
break;
}
}
// wrt, wrf
// j j
// t < f
// wrf
// er
// w < e
// er
// ett
// r < t
// ett
// rftt
// e <r
}
// w []
// e [w]
// r [e]
// t [r]
// f [t]
// Step 2: DFS to build up the output list.
for (Character c : reverseAdjList.keySet()){
boolean result = dfs(c);
if (!result){
return "";
}
}
return output.toString();
}
// Return true iff no cycles detected
private boolean dfs(Character c){
if (seen.containsKey(c)){
return seen.get(c); // if this node was grey (false), a cycle was detectee.
}
seen.put(c, false); // [w, F]
for (Character next : reverseAdjList.get(c)){ // w
boolean result = dfs(next);
if (result == false){
return false;
}
}
seen.put(c, true);
output.append(c);
return true;
}
}
// TC: O(C)
// SC: O(1) or O(U+min(U^2,N))
Kahn's Algorithm
BFS + indegree
class Solution {
public String alienOrder(String[] words) {
// Step 1: Initialize the graph and in-degree map
Map<Character, List<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
// Initialize the graph with all unique characters in words
for (String word : words) {
for (char c : word.toCharArray()) {
graph.putIfAbsent(c, new ArrayList<>());
inDegree.putIfAbsent(c, 0); // Initialize in-degree to 0 for each character
}
}
// Step 2: Build the graph based on the order of characters in words
for (int i = 0; i < words.length - 1; i++) {
String word1 = words[i];
String word2 = words[i + 1];
// Check for invalid case where word1 is a prefix of word2 and is longer
if (word1.length() > word2.length() && word1.startsWith(word2)) {
return "";
}
// Compare characters to create directed edges
for (int j = 0; j < Math.min(word1.length(), word2.length()); j++) {
char from = word1.charAt(j);
char to = word2.charAt(j);
if (from != to) {
// Create an edge from 'from' to 'to'
graph.get(from).add(to);
// Increment in-degree of 'to'
inDegree.put(to, inDegree.get(to) + 1);
break; // Only the first different character matters
}
}
}
// Step 3: Perform topological sort using Kahn's Algorithm (BFS)
Queue<Character> queue = new LinkedList<>();
StringBuilder output = new StringBuilder();
// Add all nodes with in-degree 0 to the queue
for (Character c : inDegree.keySet()) {
if (inDegree.get(c) == 0) {
queue.offer(c);
}
}
// Process nodes in BFS order
while (!queue.isEmpty()) {
char current = queue.poll();
output.append(current);
// Decrease the in-degree of neighbors
for (char neighbor : graph.get(current)) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
// If in-degree becomes 0, add it to the queue
if (inDegree.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
// Step 4: Check if we processed all nodes
if (output.length() < inDegree.size()) {
return ""; // There's a cycle, return an empty string
}
return output.toString();
}
}
// TC: O(n)
// SC: O(n)