Description

Given three strings: s1, s2, s3, determine whether s3 _is formed by the interleaving of _s1 _and _s2.

Example

For s1 ="aabcc", s2 ="dbbca"When s3 ="aadbbcbcac", returntrue.When s3 ="aadbbbaccc", returnfalse.

Solution

初始状态dp[i][0] = s3.charAt(i - 1) == s1.charAt(i - 1);dp[0][j] = s3.charAt(j - 1) == s2.charAt(j - 1);
状态方程dp[i][j] = (s3.charAt(i + j - 1) == s1.charAt(i - 1) && dp[i - 1][j]) || (s3.charAt(i + j - 1) == s2.charAt(j - 1) && dp[i][j - 1]);

public class Solution {
    /*
     * @param s1: A string
     * @param s2: A string
     * @param s3: A string
     * @return: Determine whether s3 is formed by interleaving of s1 and s2
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        // write your code here
        if (s1 == null || s2 == null || s3 == null) {
            return false;
        }

        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if (len1 + len2 != len3) {
            return false;
        }

        if (len1 == 0 && len2 == 0) {
            return true;
        }

        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        dp[0][0] = true;

        for (int i = 1; i <= len1; i++) {
            dp[i][0] = s3.charAt(i - 1) == s1.charAt(i - 1);
        }

        for (int j = 1; j <= len2; j++) {
            dp[0][j] = s3.charAt(j - 1) == s2.charAt(j - 1);
        }

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = (s3.charAt(i + j - 1) == s1.charAt(i - 1) && dp[i - 1][j]) 
                || (s3.charAt(i + j - 1) == s2.charAt(j - 1) && dp[i][j - 1]);
            }
        }

        return dp[len1][len2];
    }
}