目录
一、718. 最长重复子数组
二、712. 两个字符串的最小ASCII删除和
三、97. 交错字符串
四、10. 正则表达式匹配
五、7. 整数反转
六、8. 字符串转换整数 (atoi)
七、44. 通配符匹配
八、115. 不同的子序列
总结
在 LeetCode 的算法世界里，字符串和数组类题目是基础且高频的考点，从简单到困难层层递进，考验着我们的逻辑思维与代码功底。今天我们就来逐一拆解上图中的几道经典题目，从解题思路到 C++ 代码实现，带你吃透这些考点。
一、718. 最长重复子数组
解题思路
这道题可以用动态规划来解决。定义 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长重复子数组的长度。
- 若 nums1[i-1] == nums2[j-1] ，则 dp[i][j] = dp[i-1][j-1] + 1 ；
- 否则 dp[i][j] = 0 。
最终遍历 dp 数组找到最大值即可。
C++ 代码实现
class Solution {
public:
int findLength(vector& nums1, vector& nums2) {
int m = nums1.size(), n = nums2.size();
vector> dp(m + 1, vector(n + 1, 0));
int maxLen = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = max(maxLen, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxLen;
}
};二、712. 两个字符串的最小ASCII删除和
解题思路
同样采用动态规划。定义 dp[i][j] 表示使 s1[0..i-1] 和 s2[0..j-1] 相等所需删除字符的最小 ASCII 和。
- 若 s1[i-1] == s2[j-1] ，则 dp[i][j] = dp[i-1][j-1] ；
- 否则 dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2],-1]) 。
C++ 代码实现
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int m = s1.size(), n = s2.size();
vector> dp(m + 1, vector(n + 1, 0));
for (int i = 1; i <= m; ++i) {
dp[i][0] = dp[i - 1][0] + s1[i - 1];
}
for (int j = 1; j <= n; ++j) {
dp[0][j] = dp[0][j - 1] + s2[j - 1];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i - 1][j] + s1[i - 1], dp[i][j - 1] + s2], - 1]);
}
}
}
return dp[m][n];
}
};三、97. 交错字符串
解题思路
动态规划求解。定义 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。
- 若 s1[i-1] == s3[i+j-1] ，则 dp[i][j] = dp[i][j] || dp[i-1][j] ；
- 若 s2[j-1] == s3[i+j-1] ，则 dp[i][j] = dp[i][j] || dp[i][j-1] 。
C++ 代码实现
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (m + n != s3.size()) return false;
vector> dp(m + 1, vector(n + 1, false));
dp[0][0] = true;
for (int i = 1; i <= m; ++i) {
dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
}
for (int j = 1; j <= n; ++j) {
dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]) ||
(dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
}
}
return dp[m][n];
}
};四、10. 正则表达式匹配
解题思路
这道题是动态规划的经典难题。定义 dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。
- 若 p[j-1] != '*' ：若 s[i-1] 和 p[j-1] 匹配（相等或 p[j-1] == '.' ），则 dp[i][j] = dp[i-1][j-1] ；
- 若 p[j-1] == '*' ：
- 不使用 '*' 前面的字符： dp[i][j] = dp[i][j-2] ；
- 使用 '*' 前面的字符（需 s[i-1] 和 p[j-2] 匹配）： dp[i][j] = dp[i-1][j] 。
C++ 代码实现
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector> dp(m + 1, vector(n + 1, false));
dp[0][0] = true;
for (int j = 2; j <= n; ++j) {
dp[0][j] = dp[0][j - 2] && (p[j - 1] == '*');
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] != '*') {
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
dp[i][j] = dp[i][j - 2];
if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
};五、7. 整数反转
解题思路
反转整数时需要注意溢出问题。我们可以通过逐位取出原数的最后一位，然后拼接到结果的末尾，同时在每一步判断是否溢出。
C++ 代码实现
class Solution {
public:
int reverse(int x) {
long long res = 0;
while (x != 0) {
int digit = x % 10;
x /= 10;
res = res * 10 + digit;
if (res > INT_MAX || res < INT_MIN) {
return 0;
}
}
return (int)res;
}
};六、8. 字符串转换整数 (atoi)
解题思路
需要处理空格、符号、数字、非数字字符以及溢出情况。步骤如下：
1. 跳过前导空格；
2. 处理符号；
3. 逐个字符转换为数字，同时判断溢出。
C++ 代码实现
class Solution {
public:
int myAtoi(string s) {
int n = s.size();
int i = 0;
while (i INT_MAX) {
return INT_MAX;
}
if (res * sign < INT_MIN) {
return INT_MIN;
}
i++;
}
return res * sign;
}
};七、44. 通配符匹配
解题思路
使用动态规划。定义 dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。
- 若 p[j-1] == '*' ： dp[i][j] = dp[i-1][j] || dp[i][j-1] （ '*' 匹配多个字符或空字符）；
- 否则，若 s[i-1] == p[j-1] 或 p[j-1] == '?' ，则 dp[i][j] = dp[i-1][j-1] 。
C++ 代码实现
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector> dp(m + 1, vector(n + 1, false));
dp[0][0] = true;
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 1];
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
} else if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[m][n];
}
};八、115. 不同的子序列
解题思路
动态规划求解。定义 dp[i][j] 表示 s 的前 i 个字符中包含 t 的前 j 个字符作为子序列的个数。
- 若 s[i-1] == t[j-1] ，则 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] ；
- 否则 dp[i][j] = dp[i-1][j] 。
C++ 代码实现
class Solution {
public:
int numDistinct(string s, string t) {
int m = s.size(), n = t.size();
vector> dp(m + 1, vector(n + 1, 0));
for (int i = 0; i <= m; ++i) {
dp[i][0] = 1;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return (int)dp[m][n];
}
};总结
以上八道题目覆盖了字符串与数组类题目的多种核心解法，尤其是动态规划的大量应用。通过理解这些题目的解题思路和代码实现，相信大家在面对类似问题时能更加游刃有余。刷题之路道阻且长，坚持总结与思考，终能攻克一座座算法高峰！