| 每日一题做题记录，参考官方和三叶的题解 |
- 题目要求
- 思路一：建图+拓扑排序
- Java
- C++【超时】
- 思路二：拓扑排序+BFS
- Java
- C++
- 思路三：拓扑排序+DFS
- Java
- C++
- 总结
- 链式前向星建图，通过遍历比较两个单词字符来构建，类似双指针；
- 建图完成从字典序最小的点（入度为 0 0 0）开始进行BFS，依次入队出队，出队节点数量与总数相等则为合法拓扑图，否则有问题。
class Solution {
int N = 26, M = N * N, idx = 0, cnt = 0;
int[] head = new int[N], edge = new int[M], next = new int[M];
int[] in = new int[N], out = new int[N]; // 入度出度
boolean[] vis = new boolean[N];
// 建有向图
void add(int a, int b) {
edge[idx] = b;
next[idx] = head[a];
head[a] = idx++;
out[a]++;
in[b]++;
}
// 遍历单词a和b构建字符拓扑图
boolean build(String a, String b) {
int n = a.length(), m = b.length(), len = Math.min(n, m);
for(int i = 0; i < len; i++) {
int c1 = a.charAt(i) - 'a', c2 = b.charAt(i) - 'a';
if(c1 != c2) {
add(c1, c2);
return true;
}
}
return n <= m; // 短者应在前
}
public String alienOrder(String[] words) {
int n = words.length;
Arrays.fill(head, -1);
for(int i = 0; i < n; i++) {
for(char c : words[i].toCharArray())
if(!vis[c - 'a'] && ++cnt >= 0)
vis[c - 'a'] = true;
for(int j = 0; j < i; j++) {
if(!build(words[j], words[i]))
return "";
}
}
// BFS拓扑图输出结果
Deque que = new ArrayDeque<>();
for(int i = 0; i < 26; i++)
if(vis[i] && in[i] == 0)
que.addLast(i);
StringBuilder res = new StringBuilder();
while(!que.isEmpty()) {
int cur = que.pollFirst();
res.append((char)(cur + 'a'));
for(int i = head[cur]; i != -1; i = next[i]) {
int j = edge[i];
if(--in[j] == 0)
que.addLast(j);
}
}
return res.length() == cnt ? res.toString() : "";
}
}
- 时间复杂度： O ( n 3 ) O(n^3) O(n3)，其中 n n n是数组 w o r d s words words的长度；建图复杂度为 O ( n 3 ) O(n^3) O(n3)，BFS构建答案复杂度为 O ( n 2 ) O(n^2) O(n2)。
- 空间复杂度： O ( n 2 ) O(n^2) O(n2)
嘤嘤嘤链式前向星的C++好像就从来没搞通过……
const int N = 26, M = N * N;
class Solution {
int idx = 0, cnt = 0;
int head[N], edge[M], next[M];
int in[N], out[N]; // 入度出度
bool vis[N];
public:
// 建有向图
void add(int a, int b) {
edge[idx] = b;
next[idx] = head[a];
head[a] = idx++;
out[a]++;
in[b]++;
}
// 遍历单词a和b构建字符拓扑图
bool build(string a, string b) {
int n = a.size(), m = b.size(), len = min(n, m);
for(int i = 0; i < len; i++) {
int c1 = a[i] - 'a', c2 = b[i] - 'a';
if(c1 != c2) {
add(c1, c2);
return true;
}
}
return n <= m; // 短者应在前
}
string alienOrder(vector& words) {
int n = words.size();
memset(head, -1, N);
for(int i = 0; i < n; i++) {
for(auto c : words[i])
if(!vis[c - 'a'] && ++cnt >= 0)
vis[c - 'a'] = true;
for(int j = 0; j < i; j++) {
if(!build(words[j], words[i]))
return "";
}
}
// BFS拓扑图输出结果
queue que;
for(int i = 0; i < 26; i++)
if(vis[i] && in[i] == 0)
que.push(i);
string res;
while(!que.empty()) {
int cur = que.front();
que.pop();
res += cur + 'a';
for(int i = head[cur]; i != -1; i = next[i]) {
int j = edge[i];
if(--in[j] == 0)
que.push(j);
}
}
return res.size() == cnt ? res : "";
}
};
- 时间复杂度： O ( n 3 ) O(n^3) O(n3)，其中 n n n是数组 w o r d s words words的长度；建图复杂度为 O ( n 3 ) O(n^3) O(n3)，BFS构建答案复杂度为 O ( n 2 ) O(n^2) O(n2)。
- 空间复杂度： O ( n 2 ) O(n^2) O(n2)
- 和上面差不多，但仅记录入度。
class Solution {
Map> edges = new HashMap>();
Map in = new HashMap();
boolean valid = true;
public void build(String bef, String aft) {
int lb = bef.length(), la = aft.length();
int length = Math.min(lb, la);
int idx = 0;
while(idx < length) {
char cb = bef.charAt(idx), ca = aft.charAt(idx);
if(cb != ca) {
edges.get(cb).add(ca);
in.put(ca, in.getOrDefault(ca, 0) + 1);
break;
}
idx++;
}
if(idx == length && lb > la)
valid = false;
}
public String alienOrder(String[] words) {
int len = words.length;
for(String w : words) {
int wlen = w.length();
for(int j = 0; j < wlen; j++) {
char c = w.charAt(j);
edges.putIfAbsent(c, new ArrayList());
}
}
for(int i = 1; i < len && valid; i++)
build(words[i - 1], words[i]);
if(!valid)
return "";
Deque que = new ArrayDeque();
Set letter = edges.keySet();
for(char l : letter)
if(!in.containsKey(l))
que.offer(l);
StringBuffer res = new StringBuffer();
while(!que.isEmpty()) {
char u = que.pollFirst();
res.append(u);
List adj = edges.get(u);
for(char v : adj) {
in.put(v, in.get(v) - 1);
if(in.get(v) == 0)
que.addLast(v);
}
}
return res.length() == edges.size() ? res.toString() : "";
}
}
- 时间复杂度： O ( n × L + ∣ Σ ∣ ) O(ntimes L+|Σ|) O(n×L+∣Σ∣)，其中 n n n是数组 w o r d s words words的长度， L L L是字典中单词的平均长度， Σ Σ Σ是字典中的字母集合；构造图复杂度为 O ( n × L ) O(ntimes L) O(n×L)，DFS复杂度为 O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)。
- 空间复杂度： O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)，用于存有向图，最多包含 n − 1 n-1 n−1条边和 ∣ Σ ∣ |Σ| ∣Σ∣个节点。
class Solution {
public:
unordered_map> edges;
unordered_map in;
bool valid = true;
void build(string bef, string aft) {
int lb = bef.size(), la = aft.size();
int length = min(lb, la);
int idx = 0;
while(idx < length) {
char cb = bef[idx], ca = aft[idx];
if(cb != ca) {
edges[cb].emplace_back(ca);
in[ca] += 1;
break;
}
idx++;
}
if(idx == length && lb > la)
valid = false;
}
string alienOrder(vector& words) {
int len = words.size();
for(auto w : words) {
int wlen = w.size();
for(int j = 0; j < wlen; j++) {
char c = w[j];
if(!edges.count(c))
edges[c] = vector();
}
}
for(int i = 1; i < len && valid; i++)
build(words[i - 1], words[i]);
if(!valid)
return "";
queue que;
for(auto [e,_] : edges)
if(!in.count(e))
que.emplace(e);
string res;
while(!que.empty()) {
char u = que.front();
que.pop();
res.push_back(u);
for(char v : edges[u]) {
in[v]--;
if(in[v] == 0)
que.emplace(v);
}
}
return res.size() == edges.size() ? res : "";
}
};
- 时间复杂度： O ( n × L + ∣ Σ ∣ ) O(ntimes L+|Σ|) O(n×L+∣Σ∣)，其中 n n n是数组 w o r d s words words的长度， L L L是字典中单词的平均长度， Σ Σ Σ是字典中的字母集合；构造图复杂度为 O ( n × L ) O(ntimes L) O(n×L)，DFS复杂度为 O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)。
- 空间复杂度： O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)，用于存有向图，最多包含 n − 1 n-1 n−1条边和 ∣ Σ ∣ |Σ| ∣Σ∣个节点。
- 建图和上面差不多，但维护节点状态，包括未访问、访问中、已访问；已访问意味着该节点的所有相邻节点都已被访问。
class Solution {
static final int VISITING = 1, VISITED = 2;
Map> edges = new HashMap>();
Map states = new HashMap();
boolean valid = true;
char[] res;
int idx;
public void build(String bef, String aft) {
int lb = bef.length(), la = aft.length();
int length = Math.min(lb, la);
int idx = 0;
while(idx < length) {
char cb = bef.charAt(idx), ca = aft.charAt(idx);
if(cb != ca) {
edges.get(cb).add(ca);
break;
}
idx++;
}
if(idx == length && lb > la)
valid = false;
}
public void dfs(char u) {
states.put(u, VISITING);
List adj = edges.get(u);
for(char v : adj) {
if(!states.containsKey(v)) {
dfs(v);
if(!valid)
return;
}
else if(states.get(v) == VISITING) {
valid = false;
return;
}
}
states.put(u, VISITED);
res[idx] = u;
idx--;
}
public String alienOrder(String[] words) {
int len = words.length;
for(String w : words) {
int wlen = w.length();
for(int j = 0; j < wlen; j++) {
char c = w.charAt(j);
edges.putIfAbsent(c, new ArrayList());
}
}
for(int i = 1; i < len && valid; i++)
build(words[i - 1], words[i]);
res = new char[edges.size()];
idx = edges.size() - 1;
Set letter = edges.keySet();
for(char l : letter)
if(!states.containsKey(l))
dfs(l);
if(!valid)
return "";
return new String(res);
}
}
- 时间复杂度： O ( n × L + ∣ Σ ∣ ) O(ntimes L+|Σ|) O(n×L+∣Σ∣)，其中 n n n是数组 w o r d s words words的长度， L L L是字典中单词的平均长度， Σ Σ Σ是字典中的字母集合；构造图复杂度为 O ( n × L ) O(ntimes L) O(n×L)，DFS复杂度为 O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)。
- 空间复杂度： O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)，用于存有向图，最多包含 n − 1 n-1 n−1条边和 ∣ Σ ∣ |Σ| ∣Σ∣个节点。
class Solution {
public:
const int VISITING = 1, VISITED = 2;
unordered_map> edges;
unordered_map states;
bool valid = true;
string res;
int idx;
void build(string bef, string aft) {
int lb = bef.size(), la = aft.size();
int length = min(lb, la);
int idx = 0;
while(idx < length) {
char cb = bef[idx], ca = aft[idx];
if(cb != ca) {
edges[cb].emplace_back(ca);
break;
}
idx++;
}
if(idx == length && lb > la)
valid = false;
}
void dfs(char u) {
states[u] = VISITING;
for(char v : edges[u]) {
if(!states.count(v)) {
dfs(v);
if(!valid)
return;
}
else if(states[v] == VISITING) {
valid = false;
return;
}
}
states[u] = VISITED;
res[idx] = u;
idx--;
}
string alienOrder(vector& words) {
int len = words.size();
for(auto w : words) {
int wlen = w.size();
for(int j = 0; j < wlen; j++) {
char c = w[j];
if(!edges.count(c))
edges[c] = vector();
}
}
for(int i = 1; i < len && valid; i++)
build(words[i - 1], words[i]);
res = string(edges.size(), ' ');
idx = edges.size() - 1;
for(auto [e,_] : edges)
if(!states.count(e))
dfs(e);
if(!valid)
return "";
return res;
}
};
- 时间复杂度： O ( n × L + ∣ Σ ∣ ) O(ntimes L+|Σ|) O(n×L+∣Σ∣)，其中 n n n是数组 w o r d s words words的长度， L L L是字典中单词的平均长度， Σ Σ Σ是字典中的字母集合；构造图复杂度为 O ( n × L ) O(ntimes L) O(n×L)，DFS复杂度为 O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)。
- 空间复杂度： O ( n + ∣ Σ ∣ ) O(n+|Σ|) O(n+∣Σ∣)，用于存有向图，最多包含 n − 1 n-1 n−1条边和 ∣ Σ ∣ |Σ| ∣Σ∣个节点。
有点复杂的拓扑排序，觉得也可以单独开一篇学习，今天就复习链式前向星，后两个复杂度低点的官方方法也就先划水过了。
| 欢迎指正与讨论！ |
