LeetCode 补充题 157. 最长公共子串的构造
题目描述
[!green]
牛客原题： ✅ 补充题 157. 最长公共子串的构造
给定两个字符串
a和b，返回同时出现在二者中的最长连续子串。若有多个答案，返回第一个字符串中起点最早的一个；无公共字符时返回空字符串。字符按 Unicode 码点比较。
示例 1：
输入：
a = "xabcdz", b = "yabcq"
输出："abc"
解释："abc"同时是两个字符串的连续子串，且长度最大。
示例 2：
输入：
a = "abXYcd", b = "cdZZab"
输出："ab"
解释："ab"与"cd"都是长度为 2 的最长公共子串，选择在a中起点更早的"ab"。
提示：
- 按 Unicode 码点比较，子串必须连续。
- 同长答案选择第一个字符串中起点最早者。
- 无公共字符返回空字符串。
题意分析
公共子串必须连续，因此最后字符不相等时，不能像公共子序列那样跳过字符继续累计。把状态定义为“恰在两个指定位置结尾的公共后缀长度”，就能直接表达连续约束。
解法：倒序滚动 DP 记录最长公共后缀
核心思路
[!blue]
将两串转换为码点数组，
dp[j]在当前行表示以x[i-1]、y[j-1]结尾的最长公共后缀。两码点相等时长度为上一行dp[j-1] + 1，不等时必须归零。一维数组从右向左更新，使读取的
dp[j-1]仍属于上一行，避免将当前行刚更新的结果再次使用。dp[0]始终为 0，对应一侧空前缀。只在长度严格增大时记录
best和第一串结束位置end。第一串结束位置按递增顺序扫描，等长时更早结束也就是更早开始，所以不覆盖即可满足平局规则。最后按码点范围[end-best,end)构造结果，无匹配时得到空串。
解题步骤
- 按码点建立两串数组，用 dp[j] 表示当前两端结尾的公共后缀长度。
- 逐行扫描第一串，第二串下标倒序，匹配时延长左上旧值，失配时归零。
- 长度严格增大时记录第一串结束位置，最后按最大长度截取。
代码实现
class Solution {
public String commonSubstring(String a, String b) {
int[] x = a.codePoints().toArray();
int[] y = b.codePoints().toArray();
int[] dp = new int[y.length + 1];
int best = 0;
int end = 0;
for (int i = 1; i <= x.length; i++) {
for (int j = y.length; j >= 1; j--) {
dp[j] = x[i - 1] == y[j - 1] ? dp[j - 1] + 1 : 0;
if (dp[j] > best) {
best = dp[j];
end = i;
}
}
}
return new String(x, end - best, best);
}
}
func commonSubstring(a, b string) string {
x, y := []rune(a), []rune(b)
dp := make([]int, len(y)+1)
best, end := 0, 0
for i := 1; i <= len(x); i++ {
for j := len(y); j >= 1; j-- {
if x[i-1] == y[j-1] {
dp[j] = dp[j-1] + 1
} else {
dp[j] = 0
}
if dp[j] > best {
best = dp[j]
end = i
}
}
}
return string(x[end-best : end])
}
复杂度分析
- 时间复杂度：$O(nm)$。
- 空间复杂度：码点转换和动态规划数组的额外空间 $O(n+m)$。
关键点总结
[!green]
第一串按结束位置递增扫描，等长时不覆盖原记录，就能保留起点最早的最长结果。
易错点总结
[!yellow]
子串必须连续，不相等时归零；最长公共子序列允许跳过字符，是另一道题。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 718. 最长重复子数组 | 中等 | 同一连续后缀递推，本题用字符串并记录结束位置以返回实际内容。 |
| 1143. 最长公共子序列 | 中等 | 子序列允许跳过失配字符，子串要求连续，失配时必须清零而不是取邻格最大值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！