其实小公司根本就不欢迎大厂离职人…

最近刷脉脉，看到有人发帖说：“小公司根本不欢迎大厂离职人。”点进去一看，评论区全是共鸣，什么“太贵用不起”“不好管”“眼高手低”，仿佛大厂出身就是病毒，进门先要隔离一阵。

说实话，我以前以为，大厂履历是金字招牌，走哪都能横着走。但现实啪啪打脸，小公司看你简历上写着“BAT”，第一反应不是“哇牛”，而是“你不会看不上我们吧？”

更要命的是，那些在大厂练出来的流程思维和标准意识，在小公司压根用不上。你一套流程走完，人家老板早就拍脑袋定了方向。你说要开评审会，人家问你为啥还不开干。

所以你问我怎么看？还是那句老话——“到了新公司，就得重新做人。”

面试题：最短公共超序列

说到“最短公共超序列”（Shortest Common Supersequence，简称 SCS），我第一反应是——这玩意儿不就是“最长公共子序列”LCS 的“兄弟反着来”么 😂。不过别被名字吓到，其实 SCS 这个题啊，思路还是很清晰的，只是容易被绕进去。

咱们先来个小例子热个身：

比如你有两个字符串 str1 = "abac" 和 str2 = "cab"，目标是找出一个最短的字符串，它能包含 str1 和 str2 作为子序列。注意，是子序列，不是子串，这就意味着字符之间可以不连续，但顺序要对。

最暴力的方式就是直接拼接两个字符串，然后删冗余，比如 'abac' + 'cab' = 'abaccab'，然后把多余的删了...但这个你写个程序试试你就知道了，删着删着人都晕了。

其实解决 SCS 的套路，核心就一句话：

👉 找 LCS，然后把非 LCS 的部分拼回去。

为啥这么干？因为最长公共子序列（LCS）是两个字符串里都能保留的“最大交集”，那只要你能保留这些交集，其它字符就可以交错插入，构成一个包含两个字符串的超序列。

说人话就是，LCS 就是两个字符串共同的骨架，SCS 就是这骨架加上“漏掉的肉”。

所以，我们可以先用动态规划求出 LCS，然后再“倒推”怎么构造这个 SCS。看代码你就懂了：

defshortestCommonSupersequence(str1, str2):
    m, n = len(str1), len(str2)

# Step 1: 求 LCS 表
    dp = [[""] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i][j] + str1[i]
else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j], key=len)

    lcs = dp[m][n]  # 拿到了最长公共子序列

# Step 2: 根据 LCS 构造 SCS
    res = []
    i = j = 0
for c in lcs:
while str1[i] != c:
            res.append(str1[i])
            i += 1
while str2[j] != c:
            res.append(str2[j])
            j += 1
        res.append(c)
        i += 1
        j += 1

# 加上剩余部分
    res.extend(str1[i:])
    res.extend(str2[j:])

return''.join(res)

举个例子测试下：

print(shortestCommonSupersequence("abac", "cab"))  # 输出 "cabac"

是不是突然感觉也没那么难？😉

不过说实话，刚入门的同学常常会把这个题跟“最长公共子序列”混淆掉，尤其是那些背模板上来的，看到字符串题就上 LCS，搞一圈下来发现 LCS 不是题目答案，还很懵...

还有个常见问题是：这个算法时间复杂度是 O(mn)，是不是太慢了？

我只能说——这已经是最优解法之一了。如果你要处理上万字符的字符串，那你可能得考虑空间压缩优化（滚动数组），甚至用一些近似算法或者后缀自动机。但大部分业务系统，处理几百上千字符，老老实实写个 DP 就够了，别瞎优化成“为了快两秒写三小时”的情况 😂

所以你看，SCS 这题说简单也简单，说麻烦也确实容易绕。如果你碰到字符串算法类的面试题，这一类一定要搞清楚思路，不然面试官就会给你“套娃”问题：

“你能不能不用 LCS 直接做？可不可以只用一个字符串建 SCS？有没有在线算法？”

这时候你如果思路清晰，回答：“当然可以，但代价是性能，还是先看具体场景。”面试官立刻就知道你是懂的。