0097. Interleaving String

---

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100
• 0 <= s3.length <= 200
• s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

---

解法1

暴力计算, 遍历所有的可能.

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length() + s2.length() != s3.length())
            return false;
        return helper(s1, s2, s3, 0, 0, 0, 0, 0);
    }
    
    private boolean helper(String s1, String s2, String s3, int i1, int i2, int i3, int count1, int count2){
        if(i3 == s3.length())
            if(Math.abs(count1 - count2) <= 1)
                return true;
            else
                return false;
        
        boolean res = false;
        if(i1 < s1.length() && s1.charAt(i1) == s3.charAt(i3))
            res = helper(s1, s2, s3, i1 + 1, i2, i3 + 1, count2 + 1, count2) 
               || helper(s1, s2, s3, i1 + 1, i2, i3 + 1, count1, count2);
        
        if(!res && i2 < s2.length() && s2.charAt(i2) == s3.charAt(i3))
            res = helper(s1, s2, s3, i1, i2 + 1, i3 + 1, count1, count2 + 1) 
               || helper(s1, s2, s3, i1, i2 + 1, i3 + 1, count1, count2);
        
        return res;
    }
}

---

解法2

用二维数组DP.

把 s1 和 s2 穿插得到 s3 , 也就是各个字符的相对位置不变.

s1 的 i 位置的字符和 s2 的 j 位置的字符,是否匹配 s3 的 i + j + 1 位置的字符来判断是否可以继续匹配.

有 i 和 j 就可以确定 s3 的对应字符的位置,所以用一个二维数组就可以.

定义二维数组dp, 为了方便计算, dp的长度为 m + 1,n + 1.

dp[0][0] = true, 表示当 s1 为空,且 s2 为空时, 可以交织形成空字符串 s3.

dp[i + 1][j + 1] 表示到 s1 的 i 位置和 s2 的 j 位置为止的字符,是否可以交织成 s3 的 i + j + 1 位置为止的字符串.

     0  1  2  3  4  5 6 7 8 9
s1 : a  a [b] c  c
s2 : d [b] b  c  a
s3 : a  a  d  b [b] c b c a c

i=2, j=1为例
有两种匹配方式
1.用s1的i位置字符和s3对应字符匹配,
  当两个字符相同,并且s1的i-1位置和s2的j位置也能匹配s3时,匹配成功
  即 dp[i+1][j+1] = dp[i][j+1] && s1(i)=s3(i+j+1)

2.用s2的j位置字符和s3对应的字符匹配
  当两个字符相同,并且s2的j-1位置和s1的i位置也能匹配s3时,匹配成功
  即 dp[i+1][j+1] = dp[i+1][j] && s2(j)=s3(i+j+1)

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m + n != s3.length())
            return false;

        boolean[][] dp = new boolean[m+1][n+1];
        // 匹配空字符串
        dp[0][0] = true;

        // 只匹配s1时
        for(int i = 0; i < m; i++)
            dp[i+1][0] = dp[i][0] && s1.charAt(i) == s3.charAt(i);

        // 只匹配s2时
        for(int j = 0; j < n; j++)
            dp[0][j+1] = dp[0][j] && s2.charAt(j) == s3.charAt(j);

        for(int i = 0; i < m; i++){
            char c1 = s1.charAt(i);
            for(int j = 0; j < n; j++){
                char c2 = s2.charAt(j), c3 = s3.charAt(i + j + 1);
                dp[i+1][j+1] = (dp[i][j+1] && c1 == c3) || (dp[i+1][j] && c2 == c3);
            }
        }
        return dp[m][n];
    }
}

---

解法3

继续优化为使用两个一维数组.

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m + n != s3.length())
            return false;

        boolean[] dp = new boolean[n+1];
        dp[0] = true;

        // 不使用s1, 只匹配s2时
        for(int j = 0; j < n; j++)
            dp[j+1] = dp[j] && s2.charAt(j) == s3.charAt(j);

        for(int i = 0; i < m; i++){
            char c1 = s1.charAt(i);
            dp[0] = dp[0] && c1 == s3.charAt(i);
            for(int j = 0; j < n; j++){
                char c2 = s2.charAt(j), c3 = s3.charAt(i + j + 1);
                dp[j+1] = (dp[j+1] && c1 == c3) || (dp[j] && c2 == c3);
            }
        }
        return dp[n];
    }
}