题目形容
这是 LeetCode 上的 剑指 Offer II 114. 外星文字典 ,难度为 艰难。
Tag :「图论」、「拓扑排序」、「建图」、「图论 BFS」
现有一种应用英语字母的外星文语言,这门语言的字母程序与英语程序不同。
给定一个字符串列表 words
,作为这门语言的词典,words
中的字符串曾经 按这门新语言的字母程序进行了排序。
请你依据该词典还原出此语言中已知的字母程序,并 按字母递增程序 排列。若不存在非法字母程序,返回 ""
。若存在多种可能的非法字母程序,返回其中 任意一种 程序即可。
字符串 s
字典程序小于 字符串 t
有两种状况:
在第一个不同字母处,如果 s
中的字母在这门外星语言的字母程序中位于 t
中字母之前,那么 s
的字典程序小于 t
。
如果后面 min(s.length, t.length)
字母都雷同,那么 s.length < t.length
时,s
的字典程序也小于 t
。
示例 1:
输出:words = ["wrt","wrf","er","ett","rftt"]
输入:"wertf"
示例 2:
输出:words = ["z","x"]
输入:"zx"
示例 3:
输出:words = ["z","x","z"]
输入:""解释:不存在非法字母程序,因而返回""。
提醒:
- $1 <= words.length <= 100$
- $1 <= words[i].length <= 100$
words[i]
仅由小写英文字母组成
建图 + 拓扑排序
为了不便,咱们称 words
为 ws
,同时将两个字符串 a
和 b
之间的字典序关系简称为「关系」。
因为数组长度和每个 $ws[i]$ 的最大长度均为 $100$,咱们能够实现复杂度为 $O(n^3)$ 的算法。
首先容易想到,咱们从前往后解决每个 $ws[i]$,利用 ws
数组自身已按字典序排序,而后通过 $ws[i]$ 与 $ws[j]$ 的关系(其中 $j$ 的范畴为 $[0, i – 1]$),来构建字符之间的关系。
具体的,当咱们明确字符 $c1$ 比 $c2$ 字典序要小,能够建设从 $c1$ 到 $c2$ 的有向边,同时统计减少 $c1$ 的出度,减少 $c2$ 的入度。
当建图实现后,咱们从所有入度为 $0$ 的点开始(含意为没有比这些字符字典序更小的字符),跑一遍拓扑排序:在 BFS
过程中,一直的删点(出队的点能够看做从图中移除)和更新删除点的出边点的入度,若有新的入度为 $0$ 的点,则将其进行入队操作。
不理解拓扑排序的同学能够看前置 🧀 : 图论拓扑排序入门
若最终出队节点数量与总数量 $cnt$ 相等,阐明这是一张拓扑图(无环,字符之间不存在字典序抵触),出队的程序即是字典序,否则存在抵触,返回空串。
代码:
class Solution {
int N = 26, M = N * N, idx = 0, cnt = 0;
int[] he = new int[N], e = new int[M], ne = new int[M];
int[] in = new int[N], out = new int[N];
boolean[] vis = new boolean[N];
void add(int a, int b) {e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
out[a]++; in[b]++;
}
public String alienOrder(String[] ws) {
int n = ws.length;
Arrays.fill(he, -1);
for (int i = 0; i < n; i++) {for (char c : ws[i].toCharArray()) {if (!vis && ++cnt >= 0) vis = true;
}
for (int j = 0; j < i; j++) {if (!build(ws[j], ws[i])) return "";
}
}
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < 26; i++) {if (vis[i] && in[i] == 0) d.addLast(i);
}
StringBuilder sb = new StringBuilder();
while (!d.isEmpty()) {int u = d.pollFirst();
sb.append((char)(u + 'a'));
for (int i = he[u]; i != -1; i = ne[i]) {int j = e[i];
if (--in[j] == 0) d.addLast(j);
}
}
return sb.length() == cnt ? sb.toString() : "";
}
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;
}
}
- 工夫复杂度:令 $n$ 为数组
ws
的长度,统计字符数的复杂度为 $O(\sum_{i}^{n – 1} len(ws[i]))$,建图复杂度为 $O(n^3)$;跑拓扑序构建答案复杂度 $O(n^2)$。整体复杂度为 $O(n^3)$ - 空间复杂度:$O(C^2)$,其中 $C = 26$ 为字符集大小
最初
这是咱们「刷穿 LeetCode」系列文章的第 剑指 Offer II 114
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布