题目描述
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
题解
不能简单地认为，从s3里面过滤掉s1，把结果与s2比较久可以。 ×
动态规划！二维数组。s3要么和s1匹配一位，要么和s2匹配一位，在二维数组里体现为：上面或左边的布尔值，结合两个串中特定位置的字符，决定了当前矩阵元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if (len1 + len2 != len3)return false;
bool **dp = new bool*[len1+1];
for (int i = 0; i <= len1; i++)
dp[i] = new bool[len2+1];
for (int i = 0; i <= len1; i++)
for (int j = 0; j <= len2; j++)
dp[i][j] = false;
dp[0][0] = true;
for (int i = 1; i <= len1; i++)
if (dp[i - 1][0] && s1[i - 1] == s3[i - 1])dp[i][0] = true;
for (int j = 1; j <= len2; j++)
if (dp[0][j - 1] && s2[j - 1] == s3[j - 1])dp[0][j] = true;
for (int i = 1; i <= len1; i++)
for (int j = 1; j <= len2; j++)
if (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1])
dp[i][j] = true;
else if(dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])
dp[i][j] = true;
return dp[len1][len2];
}
|
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.3 MB, 在所有 C++ 提交中击败了94.76%的用户
666……现在我信了，遇到字符串题，先想DP。