題目
給定三個字符串 s 1 、 s 2 、 s 3 s1、s2、s3 s1、s2、s3，請你幫忙驗證 s 3 s3 s3 是否是由 s 1 s1 s1 和 s 2 s2 s2 交錯 組成的。文章來源：http://www.zghlxwxcb.cn/news/detail-828394.html
兩個字符串 s s s 和 t t t 交錯 的定義與過程如下，其中每個字符串都會被分割成若干 非空 子字符串：文章來源地址http://www.zghlxwxcb.cn/news/detail-828394.html
- s = s 1 + s 2 + . . . + s n s = s1 + s2 + ... + sn s=s1+s2+...+sn
- t = t 1 + t 2 + . . . + t m t = t1 + t2 + ... + tm t=t1+t2+...+tm
- ∣ n ? m ∣ < = 1 |n - m| <= 1 ∣n?m∣<=1
- 交錯 是 s 1 + t 1 + s 2 + t 2 + s 3 + t 3 + . . . s1 + t1 + s2 + t2 + s3 + t3 + ... s1+t1+s2+t2+s3+t3+... 或者 t 1 + s 1 + t 2 + s 2 + t 3 + s 3 + . . . t1 + s1 + t2 + s2 + t3 + s3 + ... t1+s1+t2+s2+t3+s3+...
方法
- 動態(tài)規(guī)劃
- s 1 、 s 2 、 s 3 s1、s2、s3 s1、s2、s3 長度分別為 n 1 、 n 2 、 n n1、n2、n n1、n2、n
- 定義 d p n 1 + 1 , n 2 + 2 dp_{n1+1,n2+2} dpn1+1,n2+2? 數(shù)組， d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 s 3 s3 s3 前 i + j i+j i+j 個字符是否由 s 1 s1 s1 前 i i i 個字符和 s 2 s2 s2 前 j j j 個字符交錯組成
- 若 s 3 [ i + j ? 1 ] = = s 1 [ i ? 1 ] s3[i+j-1] == s1[i-1] s3[i+j?1]==s1[i?1]，則 d p [ i ] [ j ] = d p [ i ? 1 ] [ j ] dp[i][j] = dp[i-1][j] dp[i][j]=dp[i?1][j]
- 若 s 3 [ i + j ? 1 ] = = s 2 [ j ? 1 ] s3[i+j-1] == s2[j-1] s3[i+j?1]==s2[j?1]，則 d p [ i ] [ j ] = d p [ i ] [ j ? 1 ] dp[i][j] = dp[i][j-1] dp[i][j]=dp[i][j?1]
- 空間復(fù)雜度優(yōu)化：滾動數(shù)組
- 定義 d p n 2 + 2 dp_{n2+2} dpn2+2? 數(shù)組
- d p [ j ] dp[j] dp[j] 上一次循環(huán)的值表示原來的 d p [ i ? 1 ] [ j ] dp[i-1][j] dp[i?1][j]
代碼
class Solution {
public:
// bool isInterleave(string s1, string s2, string s3) {
// int n1 = s1.size();
// int n2 = s2.size();
// int n = s3.size();
// if(n1+n2 != n)
// return false;
// vector<vector<bool>> dp(n1+1, vector<bool>(n2+1));
// dp[0][0] = true;
// for(int i = 0; i <= n1; i++){
// for(int j = 0; j <= n2; j++){
// if(i > 0){
// dp[i][j] = dp[i][j] || (dp[i-1][j] && s1[i-1] == s3[i+j-1]);
// }
// if(j > 0){
// dp[i][j] = dp[i][j] || (dp[i][j-1] && s2[j-1] == s3[i+j-1]);
// }
// }
// }
// return dp[n1][n2];
// }
bool isInterleave(string s1, string s2, string s3) {
int n1 = s1.size();
int n2 = s2.size();
int n = s3.size();
if(n1+n2 != n)
return false;
vector<bool> dp(n2+1);
dp[0] = true;
for(int i = 0; i <= n1; i++){
for(int j = 0; j <= n2; j++){
if(i > 0){
dp[j] = (dp[j] && s1[i-1] == s3[i+j-1]);
}
if(j > 0){
dp[j] = dp[j] || (dp[j-1] && s2[j-1] == s3[i+j-1]);
}
}
}
return dp[n2];
}
};
到了這里，關(guān)于力扣_字符串7—交錯字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
