我真的很喜欢这道题。
我面试被人问到过这道题，当时给出了整体思路和一个可行解法。
面试官嫌弃我在建图时用了recursion容易出错，教我了另外一种解法，按他的思路把代码写出来了，不过面试还是没过。悟到题不是会做就可以了，还要给漂亮的或者至少易懂的解法。
这就是在面试中学习的例子。面试挂了不过我这个解法学到了。
他教我的做法就是下面代码里面那个compareTwoWords的函数。
这里讲外星人字典的两种做法。
首先不管什么做法都要先建图。
建图可以把每个相领的单词做比较，能得出他俩为什么不同得出两个字母的先后顺序。
有了图之后有两种做法。
1。 我们用topological order， 先看那些入度为0的点。这些点都可以放进去。
然后把这些入度为0的点的下一字母的入度减1， 当减为0呀， 这个字母也可以丢进来 。
2。 DFS： 这个比较难理解。
我们用相同的图，对于图上每一个点， 我们深度优先搜索到它的尽头。它的尽头肯定可以放在最后。
等尽头的都放完了，他的上一层也可以放了。
对于每一个节点，我们先处理好它的孩子，等它的孩子孙子都处理好了确保所有依赖于它的都放在它的后面，再把它放进来。把它放进来之后标记一下，下次不要再访问它了。
这里要处理有环的情况，如果在往子孙方向去的时候子孙又回溯到了那些还没 处理完的结点，则表明有环。
请参考这个高票答案。很赞
https://leetcode.com/problems/alien-dictionary/discuss/70115/3ms-Clean-Java-Solution-(DFS)
他这个DFS写的是真的很赞
现在帖一下我的代码。 DFS的和上面的链接基本一样。
class Solution {
public String alienOrder(String[] words) {
boolean[][] graph = new boolean[26][26];
int[] visited = new int[26];
Arrays.fill(visited, -1);
buildGraph(words, graph, visited);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
if (visited[i] == 0) {
if (!dfs(graph, visited, i, sb)) return "";
}
}
return sb.reverse().toString();
}
private boolean dfs(boolean[][] graph, int[] visited, int i, StringBuilder sb) {
visited[i] = 1;
for (int j = 0; j < 26; j++) {
if (visited[j] == -1) continue;
if (!graph[i][j]) continue;
if (visited[j] == 1) return false;
if (visited[j] == 0) {
if (!dfs(graph, visited, j, sb)) return false;
}
}
sb.append((char) ('a' + i));
visited[i] = 2;
return true;
}
private void buildGraph(String[] words, boolean[][] graph, int[] visited) {
for (int i = 0; i < words.length - 1; i++) {
int[] relation = compareWords(words[i], words[i + 1]);
if (relation == null) continue;
graph[relation[0]][relation[1]] = true;
markLetters(words[i], visited);
}
if (words.length != 0) markLetters(words[words.length - 1], visited);
}
private void markLetters(String w1, int[] visited) {
for (char ch : w1.toCharArray()) visited[ch - 'a'] = 0;
}
private int[] compareWords(String w1, String w2) {
int pt1 = 0, pt2 = 0;
while (pt1 < w1.length() && pt2 < w2.length()) {
if (w1.charAt(pt1) != w2.charAt(pt2)) {
return new int[] {w1.charAt(pt1) - 'a', w2.charAt(pt2) - 'a'};
}
pt1++;
pt2++;
}
return null;
}
}
这里帖一下我的BFS的写法。
class Solution {
public String alienOrder(String[] words) {
boolean[][] graph = new boolean[26][26];
int[] visited = new int[26];
Arrays.fill(visited, -1);
buildGraph(words, graph, visited);
return bfs(graph, visited);
}
private String bfs(boolean[][] graph, int[] visited) {
int[] inDegrees = new int[26];
int cnt = 0;
Queue<Integer> zeroInDegrees = new LinkedList<>();
StringBuilder sb = new StringBuilder();
for (int child = 0; child < 26; child++) {
if(visited[child] == -1){
inDegrees[child] = -1;
continue;
}
for (int parent = 0; parent < 26; parent++) {
if (graph[parent][child]) inDegrees[child]++;
}
cnt++;
if (inDegrees[child] == 0) {
zeroInDegrees.offer(child);
sb.append((char) (child + 'a'));
}
}
while (!zeroInDegrees.isEmpty()) {
int parent = zeroInDegrees.poll();
for (int child = 0; child < 26; child++) {
if (graph[parent][child]) {
inDegrees[child] --;
if (inDegrees[child] == 0) {
zeroInDegrees.offer(child);
sb.append((char) (child + 'a'));
}
}
}
}
if (sb.length() != cnt) return "";
return sb.toString();
}
private void buildGraph(String[] words, boolean[][] graph, int[] visited) {
for (int i = 0; i < words.length - 1; i++) {
int[] relation = compareWords(words[i], words[i + 1]);
if (relation == null) continue;
graph[relation[0]][relation[1]] = true;
markLetters(words[i], visited);
}
if (words.length != 0) markLetters(words[words.length - 1], visited);
}
private void markLetters(String w1, int[] visited) {
for (char ch : w1.toCharArray()) visited[ch - 'a'] = 0;
}
private int[] compareWords(String w1, String w2) {
int pt1 = 0, pt2 = 0;
while (pt1 < w1.length() && pt2 < w2.length()) {
if (w1.charAt(pt1) != w2.charAt(pt2)) {
return new int[] {w1.charAt(pt1) - 'a', w2.charAt(pt2) - 'a'};
}
pt1++;
pt2++;
}
return null;
}
}
这道题有个follow up就是 求有多少种可能解。
我想了一下bfs分层做，数一下每一层有几个，然后把每一层求阶乘，然后再乘起来，好像是不行的，因为对一个字母来说，它可能一定要排在他父亲的后面，但它不一定要排在它叔叔的后面，即使它的父亲和它的叔叔是在同一层。
用DP可以做。
DP[state][bit]
我们用state表示有哪些字母在。如果state & (1 << bit) > 0，就表示第bit个字母在。
DP的定义是以第bit个字母结尾的，包含state上所有字母的组合的所有可能解的数量。
Induction rule看下面的注释。
测了几个小的test case是能跑过的。
public long findAllVariations(int[][] graph, int[] marker) {
//marker代表哪个字母出现过，没出现过就是-1;
// 先把图缩小，不是26个字母都出现过，没出现的就不算了。
//reduce the map size from 26 to number of letters actually appeared
Map<Integer, Integer> idMap = new HashMap<>();
int index = 0;
for (int i = 0; i < 26; i++) {
if (marker[i] != -1) idMap.put(i, index++);
}
int[][] smallGraph = new int[index][index];
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
if (graph[i][j] == 1) {
smallGraph[idMap.get(i)][idMap.get(j)] = 1;
}
}
}
int N = index; //N is the number of letters appeared
//set up the variables for dp(it is actually recursion with memorization)
int state = 0;
for (int i = 0; i < N; i++) state += (1 << i);
long[][] dp = new long[state + 1][N];
for (int j = 0; j < state + 1; j++) Arrays.fill(dp[j], -1L);
//dp[state][i] 代表还剩state位表示的所有字母，和以第i个字母结尾的所有可能的组合。
//如果 state & (1 << i) > 0 代表第i个字母在这个组合里面。
// run recursion with memorization
for (int i = 0; i < N; i++) {
recursionWithMemo(dp, state, i, N, smallGraph);
}
//整理结果
long ans = 0L;
for (int i = 0; i < N; i++) ans += dp[state][i];
return ans;
}
private long recursionWithMemo(long[][] dp, int state, int bit, int N, int[][] graph) {
//如果已经算过，就不再算了
if (dp[state][bit] != -1 ) return dp[state][bit];
//初始化为0
dp[state][bit] = 0L;
//如果state里面不包含当前字母(bit)的所有上级字母，则为0，返回。
for (int i = 0; i < N; i++) {
if (graph[i][bit] == 1 && ((state & (1 << i)) == 0)) {
return dp[state][bit]; //为 0
}
}
// base case
//如果就bit位上一个字母，而且包含他上组的所有字母（其实就是入度为0的case）
if (state == (1 << bit)) {
dp[state][bit] = 1L;
return dp[state][bit];
}
// induction rule
// dp[state][bit] = Sum (dp[state - (1 << bit)][0 -> N - 1])
// 除掉 当前字母后，所有可能的数目和
int upperState = state - (1 << bit);
for (int i = 0; i < N; i++) {
if ((upperState & (1 << i)) > 0) {
dp[state][bit] += recursionWithMemo(dp, upperState, i, N, graph);
}
}
return dp[state][bit];
}
