Monday, March 4, 2013

[LeetCode] Interleaving String

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