Thought:
Dynamic Programming.
Code:
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int l1 = s1.length();
int l2 = s2.length();
int l3 = s3.length();
if (l1 + l2 != l3) return false;
if (l1 == 0) return s2.equals(s3);
if (l2 == 0) return s1.equals(s3);
if (s1.charAt(l1 - 1) == s3.charAt(l3 - 1) && s2.charAt(l2 - 1) == s3.charAt(l3 - 1)) {
return isInterleave(s1.substring(0, l1 - 1), s2, s3.substring(0, l3 - 1)) || isInterleave(s1, s2.substring(0, l2 - 1), s3.substring(0, l3 - 1));
}else if (s1.charAt(l1 - 1) == s3.charAt(l3 - 1)) {
return isInterleave(s1.substring(0, l1 - 1), s2, s3.substring(0, l3 - 1));
}else if (s2.charAt(l2 - 1) == s3.charAt(l3 - 1)) {
return isInterleave(s1, s2.substring(0, l2 - 1), s3.substring(0, l3 - 1));
}else {
return false;
}
}
}
No comments:
Post a Comment