Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 =
s2 =
Given:
s1 =
"aabcc"
,s2 =
"dbbca"
,
When s3 =
When s3 =
"aadbbcbcac"
, return true.When s3 =
"aadbbbaccc"
, return false.
Solution 1: Use DP, dp[i][j] store the result of s1[0...i) s2[0..j) and s3[0...i+j) is interleaving or not. There will be 2 case, s1.charAt(i-1)==s3.charAt(i+j-1) or s2.charAt(j-1)==s3.charAt(i+j-1). Details below:
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m=s1.length();
int n=s2.length();
if (m+n!=s3.length()) return false;
boolean[] dp=new boolean[n+1];
for (int i=0; i<=m; i++) {
for (int j=0; j<=n; j++) {
if (i==0) {
if (j==0) dp[j]=true;
else dp[j]=s2.charAt(j-1)==s3.charAt(j-1) && dp[j-1];
}
else if (j==0) dp[j]=s1.charAt(i-1)==s3.charAt(i-1) && dp[j];
else dp[j]=(s1.charAt(i-1)==s3.charAt(i+j-1) && dp[j]) || (s2.charAt(j-1)==s3.charAt(i+j-1) && dp[j-1]);
}
}
return dp[n];
}
}
没有评论:
发表评论