用最少数据记录两个字符串数组的差异
哪些公司问过
答案要点
- 先澄清是否关心顺序:集合语义用哈希求双向差集
- 顺序重要时求最短编辑脚本,与 LCS 互补
- LCS 动态规划 O(mn);Myers 算法复杂度与差异规模相关
- 只记录插入删除操作与位置,相同内容用引用代替
- 字典编码、位置差分编码再叠加通用压缩,进一步减小体积
易错点
- 默认当集合处理,忽略了顺序和重复元素
- 直接存 B 的全量或把相同部分也写进记录
- 只给 O(mn) DP,不考虑大数组下的内存问题
面试官常见追问
- LCS 的 DP 怎么写?
- 如果数组很大、差异很小,怎么更快?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场