For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Idea: Dynamic programming. Let dp[i][j] denote whether s3[0...i+j-1] is a interleaving of s1[0...i-1] and s2[0...j-1]. Then we have the following recursion function:
dp[i][j]==true requires either
1) dp[i-1][j]==true && s1[i-1]==s3[j+i-1];
or 2) dp[i][j]==true && s2[i-1]==s3[i+j-1].
For the first row and first column, since the other string is empty, actually we are doing string.equals() one character by one character.
Time: O(n^2) Space: O(n^2)
Code:
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m=s1.length();
int n=s2.length();
if(s3.length()!=m+n)
return false;
boolean[][] dp=new boolean[m+1][n+1];
dp[0][0]=true;
for(int i=0;i<m;i++)
{
if(s1.charAt(i)==s3.charAt(i))
dp[i+1][0]=true;
else
break;
}
for(int j=0;j<n;j++)
{
if(s2.charAt(j)==s3.charAt(j))
dp[0][j+1]=true;
else
break;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=(dp[i-1][j]&&s1.charAt(i-1)==s3.charAt(j+i-1))
||(dp[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1));
}
}
return dp[m][n];
}
}
No comments:
Post a Comment