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.

Analysis

DP:

• State:dp[i][j] 构成s1的前i个字符和s2的前j个字符能否构成s3的前i+j个字符
• Transfer:
  • 如果要true只有两种情况：
  • s3的最后一个字母和s1的最后一个字母相同，并且s3不考虑最后一个字母可以由s1不考虑最后一个字母和s2一起组成。既：dp[i-1][j]==true
  • s3的最后一个字母和s2的最后一个字母相同，并且s3不考虑最后一个字母可以由s1和s2不考虑最后一个字母一起组成。既：dp[i][j-1]==true
• Initialize: (第一行&第一列)
  • dp[0][0] = true
  • dp[i][0]:s3.substring(0, j).equals(s2.substring(0,j))
  • dp[0][j]:s3.substring(0, i).equals(s1.substring(0,i))
• Return: dp[s1.length][s2.length]

Code

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();

        if (len1==0) return s2.equals(s3);
        if (len2==0) return s1.equals(s3);
        if (len1+len2!=len3) return false;

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

        for (int i=0; i<=len1; i++){
            for (int j=0; j<=len2; j++){
                if (i==0) dp[i][j] = s3.substring(0, j).equals(s2.substring(0,j));
                else if (j==0) dp[i][j] = s3.substring(0, i).equals(s1.substring(0,i));
                else {
                    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];
    }
}

Reference

Yuanbin