For example,
Given:
s1 =
"aabcc"
,s2 =
"dbbca"
,
When s3 =
"aadbbcbcac"
, return true.When s3 =
"aadbbbaccc"
, return false.public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
if(s1==null || s2==null || s3==null || s1.length()+s2.length()!=s3.length()) {
return false;
}
boolean match[][] = new boolean[s1.length()+1][s2.length()+1];
match[0][0] = true;
for(int i=1;i<=s1.length();i++) {
match[i][0] = match[i-1][0] && (s1.charAt(i-1)==s3.charAt(i-1));
}
for(int i=1;i<=s2.length();i++) {
match[0][i] = match[0][i-1] && (s2.charAt(i-1)==s3.charAt(i-1));
}
for(int i=0;i<s1.length();i++) {
for(int j=0;j<s2.length();j++) {
match[i+1][j+1] = (s3.charAt(i+j+1)==s1.charAt(i) && match[i][j+1]) ||
(s3.charAt(i+j+1)==s2.charAt(j) && match[i+1][j]);
}
}
return match[s1.length()][s2.length()];
}
}
没有评论:
发表评论