97. Interleaving String
难度:Hard
刷题内容
原题连接
- https://leetcode.com/problems/interleaving-string/
内容描述
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
˼· **- ʱ�临�Ӷ�: O(N^2)*- �ռ临�Ӷ�: O(N^2)***
һ���ñ����ķ���ȥ�����⣬ʱ�临�Ӷ�ΪO(2^n)��ʱ�临�Ӷ�Ϊָ�������϶���ʱ内容描述ǿ����ö�̬�滮��ʱ�临�Ӷ��Ż���O(n^2)���̬�滮�Ĺؼ������ҵ�״̬ת�Ʒ��̣������ά���� dp[i][j]����ʾ s1[i]�� s2[j]֮����Ӵ��Ƿ������s3[i + j]内容描述�Ǿ���д��״̬ת�Ʒ��̣�dp[i][j] = (s1[i] == s3[i + j] && dp[i + 1][j]) || (s2[j] == s3[i + j] && dp[i][j + 1])
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int l1 = s1.length(),l2 = s2.length(),l3 = s3.length();
if(l1 + l2 != s3.length())
return 0;
int dp[l1 + 2][l2 + 2];
memset(dp,0,sizeof(dp));
dp[l1][l2] = 1;
for(int i = l1;i >= 0;--i)
for(int j = l2;j >= 0;--j)
{
if(i < l1 && s1[i] == s3[i + j] && dp[i + 1][j])
dp[i][j] = 1;
if(j < l2 && s2[j] == s3[i + j] && dp[i][j + 1])
dp[i][j] = 1;
}
return dp[0][0];
}
};
