97. 交错字符串

题目链接：97. 交错字符串 - 力扣（LeetCode）

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

‘解析：二维dp

dp[i][j]代表s1前i个和s2前j个是否能组成s3的i+j个

状态转移方程就很简单了，

但这一题要求空间限制，可以观察到dp其实只记录一维就可以，因为用到了i-1或者j-1

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n = s1.size(), m = s2.size(), k = s3.size();if (n + m != k) return false;else if (n == 0) return s2 == s3;else if (m == 0) return s1 == s3;int dp[105][105];dp[0][0] = true;for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {if (i == 0 && j == 0) continue;if (i == 0) {dp[i][j] = dp[i][j - 1] && (s2[j - 1] == s3[j - 1]);} else if (j == 0) {dp[i][j] = dp[i - 1][j] && (s1[i - 1] == s3[i - 1]);} else {int id = i + j - 1;dp[i][j] = dp[i][j - 1] && (s2[j - 1] == s3[id]) || dp[i - 1][j] && (s1[i - 1] == s3[id]);}}}return dp[n][m];}
};

　　

 

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n = s1.size(), m = s2.size(), k = s3.size();if (n + m != k) return false;else if (n == 0) return s2 == s3;else if (m == 0) return s1 == s3;int dp[105];dp[0] = true;for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {if (i == 0 && j == 0) continue;if (i == 0) {dp[j] = dp[j - 1] && (s2[j - 1] == s3[j - 1]);} else if (j == 0) {dp[j] = dp[j] && (s1[i - 1] == s3[i - 1]);} else {int id = i + j - 1;dp[j] = dp[j - 1] && (s2[j - 1] == s3[id]) || dp[j] && (s1[i - 1] == s3[id]);}}}return dp[m];}
};