写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【动态规划】【字符串】
题目来源
97. 交错字符串
解题思路
方法一:动态规划
首先进行特判,记字符串 s1
的长度、字符串 s2
的长度、字符串 s3
的长度分别为 m
、n
和 t
。如果 m + n != t
,那么 s3
一定无法由 s1
和 s2
交错组成。
定义状态
在 m + n = t
时,定义 f[i][j]
表示 s1
的前 i
个字符和 s2
的前 j
字符是否能交错组成 s3
的前 i+j
个字符。
转移关系
如果 s1
的第 i
个字符和 s3
的第 i+j
个字符相同,那么 s1
的前 i
个字符和 s2
的前 j
字符是否能交错组成 s3
的前 i+j
个字符 取决于 s1
的前 i-1
个字符和 s2
的前 j
字符是否能交错组成 s3
的前 i+j-1
个字符,即有:
KaTeX parse error: Expected 'EOF', got '&' at position 22: …j] = f[i-1][j] &̲ (s_1[i-1] == s…
同理,如果 s2
的第 j
个字符和 s3
的第 i+j
个字符相同,那么 s1
的前 i
个字符和 s2
的前 j
字符是否能交错组成 s3
的前 i+j
个字符 取决于 s1
的前 i
个字符和 s2
的前 j-1
字符是否能交错组成 s3
的前 i+j-1
个字符,即有:
KaTeX parse error: Expected 'EOF', got '&' at position 22: …j] = f[i][j-1] &̲ (s_2[j-1] == s…
base case
边界条件为 f[0][0] = true
。
最后返回
最终返回 f[m][n]
,表示字符串 s3
是否可以右字符串 s1
和 s2
交错形成。
朴素实现代码
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size(), t = s3.size();
if (m + n != t) return false;
vector<vector<int>> f(m+1, vector<int>(n+1, false));
f[0][0] = true; // base case 空字符串可以交错形成空字符串
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
int p = i + j - 1;
if (i > 0) {
f[i][j] |= f[i-1][j] && (s1[i-1] == s3[p]);
}
if (j > 0) {
f[i][j] |= f[i][j-1] && (s2[j-1] == s3[p]);
}
}
}
return f[m][n];
}
};
使用滚动数组优化空间复杂度。 因为这里数组 f
的第 i
行只和第 i−1
行相关,所以我们可以用滚动数组优化这个动态规划,这样空间复杂度可以变成
O
(
m
)
O(m)
O(m)。
空间优化代码
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size(), t = s3.size();
if (m + n != t) return false;
vector<int> f(n+1, false);
f[0] = true; // base case 空字符串可以交错形成空字符串
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
int p = i + j - 1;
if (i > 0) {
f[j] &= (s1[i-1] == s3[p]);
}
if (j > 0) {
f[j] |= f[j-1] && (s2[j-1] == s3[p]);
}
}
}
return f[n];
}
};
复杂度分析
时间复杂度:
O
(
m
n
)
O(mn)
O(mn),
m
m
m 为字符串 s1
的长度,
n
n
n 为字符串 s2
的长度。
空间复杂度:按行进行滚动数组优化后的空间复杂度为 O ( m ) O(m) O(m),朴素动态规划的时间复杂度为 O ( m n ) O(mn) O(mn)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。文章来源:https://www.toymoban.com/news/detail-852176.html
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-852176.html
到了这里,关于【面试经典150 | 动态规划】交错字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!