leetcode — interleaving-string

/**
 * Source : https://oj.leetcode.com/problems/interleaving-string/
 *
 *
 * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
 *
 * For example,
 * Given:
 * s1 = "aabcc",
 * s2 = "dbbca",
 *
 * When s3 = "aadbbcbcac", return true.
 * When s3 = "aadbbbaccc", return false.
 *
 */
public class InterLeavingString {


    /**
     * 判断字符串s3是否由s1和s2交织而成
     * 直接从s3里面移除s1，然后判断剩下的字符串是否和s2相同，这种做法是行不通的，比如s1="c",s2="ca",s3="cac"，
     *      如果移除s1，剩下就是ac明显和s2不等，但是s3确实可以由s1和s2交织而成
     *
     * 这里使用递归的方法解，但是时间复杂度较高
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterLeaveByRecursion (String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        int s1Index = 0;
        int s2Index = 0;
        for (int i = 0; i < s3.length(); i++) {
            if ((s1Index < s1.length() && s1.charAt(s1Index) == s3.charAt(i)) && (s2.length() <= s2Index || s2.charAt(s2Index) != s3.charAt(i))) {
                s1Index++;
            } else if ((s1.length() <= s1Index || s1.charAt(s1Index) != s3.charAt(i)) && (s2.length() > s2Index && s2.charAt(s2Index) == s3.charAt(i))) {
                s2Index++;
            } else if ((s1.length() > s1Index && s1.charAt(s1Index) == s3.charAt(i)) && (s2.length() > s2Index && s2.charAt(s2Index) == s3.charAt(i))) {
                if (!isInterLeaveByRecursion(s1.substring(s1Index + 1), s2.substring(s2Index), s3.substring(i + 1))) {
                    return isInterLeaveByRecursion(s1.substring(s1Index), s2.substring(s2Index + 1), s3.substring(i + 1));
                }
                return true;
            } else {
                return false;
            }
        }
        return s1Index == s1.length() && s2.length() == s2Index;
    }

    /**
     * 使用动态规划解决
     *
     * 二位数组用来存储s1和s2每一个字符和s3字符的匹配情况，match[s1.length+1][s2.length+1]
     * match[i][j]表示s1[0-i]，s2[0-j]可以交织成s3[0-(i+j-1)]
     * match[i][j] = (match[i-1][j] && s3[i+j-1] == s1[i]) || (match[i][j-1] && s3[i+j-1] == s2[j])
     *
     * 初始情况：
     * i == 0 && j == 0,match[0][0] = true
     * i == 0 && j != 0
     *      s2[j] == s3[j], match[0][j] |= match[0][j-1]
     *      s2[j] != s3[j], match[0][j] = false
     * 
     * j == 0 && i != 0
     *      s1[i] == s3[i], match[i][0] |= match[i-1][0]
     *      s1[i] != s3[i], match[i][0] = false
     *
     * @param s1
     * @param s2
     * @param s3
     * @return
     */
    public boolean isInterleaveByDP (String s1, String s2, String s3) {
        if (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++) {
            if (s1.charAt(i-1) == s3.charAt(i-1)) {
                match[i][0] = true;
            } else {
                break;
            }
        }

        for (int j = 1; j <= s2.length(); j++) {
            if (s2.charAt(j-1) == s3.charAt(j-1)) {
                match[0][j] = true;
            } else {
                break;
            }
        }

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i-1) == s3.charAt(i+j-1)) {
                    match[i][j] = match[i-1][j] || match[i][j] ;
                }
                if (s2.charAt(j-1) == s3.charAt(i+j-1)) {
                    match[i][j] = match[i][j-1] || match[i][j] ;
                }
            }
        }
        return match[s1.length()][s2.length()];
    }




    public static void main(String[] args) {
        InterLeavingString interLeavingString = new InterLeavingString();
        System.out.println(interLeavingString.isInterLeaveByRecursion("aabcc", "dbbca", "aadbbcbcac") + "---true");
        System.out.println(interLeavingString.isInterLeaveByRecursion("aabcc", "dbbca", "aadbbbaccc") + "---false");
        System.out.println(interLeavingString.isInterLeaveByRecursion("c", "ca", "cac") + "---true");
        System.out.println(interLeavingString.isInterLeaveByRecursion("", "", "") + "---true");

        System.out.println();
        System.out.println(interLeavingString.isInterleaveByDP("aabcc", "dbbca", "aadbbcbcac") + "---true");
        System.out.println(interLeavingString.isInterleaveByDP("aabcc", "dbbca", "aadbbbaccc") + "---false");
        System.out.println(interLeavingString.isInterleaveByDP("c", "ca", "cac") + "---true");
        System.out.println(interLeavingString.isInterleaveByDP("", "", "") + "---true");
    }

}