题目形容

这是 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[26];    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[c - 'a'] && ++cnt >= 0) vis[c - 'a'] = 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(n^2)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 剑指 Offer II 114 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干的材料可拜访排版精明的 合集新基地

本文由mdnice多平台公布