2.2 亿彩票公布调查结果
昨天，闹得沸沸扬扬的《10 万中 2.2 亿》的彩票事件，迎来了官方公告。
简单来说，调查结果就是：一切正常，合规合法。
关于福利彩票事件，之前的推文我们已经分析过。
甚至在后面出现《双色球 6.8 亿》事件时，还用类似的逻辑分析写了回答发到过某乎：
这次所谓调查通报，其实还是没有走出使用「公信力」来进行自证的圈子。
该说的都说过了，本次不再点评。
...
回归主线。
今天接着看「华为 OD」一面算法原题。
昨天分享了一道「子序列」相关的「华为 OD」一面算法原题，很多网友表示不可思议。
那道题在 LeetCode 中是 Hard，现在连 OD 都这么卷了吗？
是的，OD 都开始卷了。
这其实不难理解。
算法在笔试面试中出现，主要是起到一个「过滤」的作用。
以前面试算法题难度普遍没有很高，是因为出到普通难度，也足以产生过滤作用，再难可能就没有候选人做出来，反而起不到过滤效果。
现如今，随着互联网大厂的各种裁员，加上应届大学生毕业人数屡创新高，连华为 OD 岗位都供远大于求了，因此算法题难度也上来了。
题目描述
平台：LeetCode
题号：943
给定一个字符串数组 words，找到以 words 中每个字符串作为子字符串的最短字符串。
如果有多个有效最短字符串满足题目条件，返回其中任意一个即可。
我们可以假设 words 中没有字符串是 words 中另一个字符串的子字符串。
示例 1：
输入：words = ["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。
示例 2：
输入：words = ["catg","ctaagt","gcta","ttca","atgcatc"]
输出："gctaagttcatgcatc"
提示：
- words[i] 由小写英文字母组成
-
words 中的所有字符串互不相同
状压 DP
为了方便，将 words 记为 ws。
预处理二维数组 g 来表示字符串 ws[i] 和 ws[j] 的重叠部分的长度：若 g[i][j] = len 代表字符串 ws[i] 长度为 len 的后缀与字符串 ws[j] 长度为 len 的前缀相同。
另外用一个二进制数 status 来代表当前超级串 ans 对 ws 的使用（覆盖）情况：若 status 的第 i 位为 1 代表字符串 ws[i] 已被使用（即 ws[i] 已是 ans 的子串），若 status 的第 i 位为 0 代表 ws[i] 未被使用。
我们知道，当所有的 时，代表所有拼接方式长度均为 ，即不能通过产生重叠部分来缩短超级串的长度。
因此，最小化超级串 ans 的长度等价于最大化重叠部分的长度。
定义 代表当前状态为 s 且当前最后一个使用到的字符串为 ws[i] （当前超级串 ans 的结尾部分为 ws[i]）时的最大重合长度。
最终超级串的长度为所有字符串的总长度 减去最大重合长度 。
不失一般性考虑 可用于更新哪些状态，我们可枚举接在字符串 ws[i] 后面的字符串 ws[j] 为何值：
- 由于每个字符串只能使用一次，转移需要满足 s 的第 i 位为 ， s 的第 j 位为 的前提条件，含义为 ws[i] 已被使用，而 ws[j] 未被使用
- 满足前提条件 ，代表 ws[j] 可接在 ws[i] 后面，此时有状态转移方程：
接下来，考虑如何构建具体方案。
使用二维数组 记录每个状态是由哪个前驱转移而来：若有 ，代表取得最大重叠长度过程中，字符串 ws[j] 接在 ws[i] 后面。
我们从后往前对 ans 进行构造，若 ans = ws[0] + ws[1] + ... + ws[k - 1] + ws[k]，我们是先找 ws[k]，再通过 ws[k] 找 ws[k - 1]，直到将整个 ans 构建出来。
构造过程中使用变量解释如下：
- ans 为具体的超级串
- status 代表当前还有哪些字符串待拼接到，初始化为 ，代表还没有任何字符串拼接到 ans 中
- idx 代表当前处理到的字符串下标，初始化通过遍历所有的 找到合适的 作为 idx
-
last 代表前一个处理到字符串下标，初始化为
-1
一些细节：当 last 不为初始值 -1 时，需要跳过 ws[idx] 与 ws[last] 的重复部分进行拼接。
Java 代码：
class Solution {
public String shortestSuperstring(String[] ws) {
int n = ws.length, mask = 1
