mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
47 lines
2.0 KiB
Markdown
47 lines
2.0 KiB
Markdown
# [97. Interleaving String](https://leetcode.cn/problems/interleaving-string/)
|
||
|
||
# 思路
|
||
仔细分析问题不难发现会涉及到大量子问题，所以我们考虑用动态规划求解。我们定义 dp[i][j] 表示 s1 的前 i 个元素和 s2 的前 j 个元素是否能交错组成 s3 的前 i + j 个元素。可得到初始状态和状态转移方程为：
|
||
```
|
||
初始态（即都为空串）：dp[0][0] = true
|
||
转移方程：dp[i][j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])
|
||
```
|
||
再考虑下边界条件就不难写出代码。另外由于 dp[i][j] 只和左上元素有关，故可以考虑使用滚动数组优化空间复杂度为O(s2.size())。
|
||
|
||
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
bool isInterleave(string s1, string s2, string s3) {
|
||
if(s1.size() + s2.size() != s3.size()) return false;
|
||
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
|
||
if(n1 == 0) return s2 == s3;
|
||
if(n2 == 0) return s1 == s3;
|
||
|
||
// vector<vector<bool>>dp(n1 + 1, vector<bool>(n2 + 1, false));
|
||
// for(int i = 0; i <= n1; i++){
|
||
// for(int j = 0; j <= n2; j++){
|
||
// if(i == 0 && j == 0) dp[i][j] = true;
|
||
// else if(i > 0 && dp[i-1][j] && s3[i+j-1] == s1[i-1]) dp[i][j] = true;
|
||
// else if(j > 0 && dp[i][j-1] && s3[i+j-1] == s2[j-1]) dp[i][j] = true;
|
||
// // else dp[i][j] = false;
|
||
// }
|
||
// }
|
||
// return dp[n1][n2];
|
||
|
||
// 滚动数组空间优化
|
||
vector<bool>dp(n2 + 1, false);
|
||
for(int i = 0; i <= n1; i++){
|
||
for(int j = 0; j <= n2; j++){
|
||
if(i == 0 && j == 0) dp[j] = true;
|
||
else if(i > 0 && dp[j] && s3[i+j-1] == s1[i-1]) dp[j] = true;
|
||
else if(j > 0 && dp[j-1] && s3[i+j-1] == s2[j-1]) dp[j] = true;
|
||
else dp[j] = false; // 注意这里需重置成false, 因为dp[i-1][j]可能等于true
|
||
}
|
||
}
|
||
return dp[n2];
|
||
}
|
||
};
|
||
``` |