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.

[解题思路]

分析

题目给定3个字符串(s1,s2,s3)，看s3是否是有s1和s2通过交织可以得到。





可以这么来看这个问题，每次从s3开头拿出来一个字符，如果s1的开头或者s2的开头有这个字符的话，就消掉相应的字符，把这个操作记为del。

这样看待这个问题的话，好像挺简单的，很直观。

但是当遇到case：s1=aa,s2=ab,s3=abaa，的时候可以看出当s1和s2同时可以进行del操作的时候，选择就成了一个必须考虑的问题。

假如最开始那个a，消掉了s1中的第一个a，那么就进行不下去了。

<br>

所以最后这个问题其实并不那么简单，假如函数

bool isInterleaving(string&s1,int len1,string&s2,int len2,string&s3,int len3);

表示子问题：si取前leni个字符的话，那么实际上可以得到这样的一个公式：

isInterleaving(s1,len1,s2,len2,s3,len3)=(s3.lastChar == s1.lastChar)&& isInterleaving(s1,len1 -1,s2,len2,s3,len3 -1)||(s3.lastChar == s2.lastChar)&& isInterleaving(s1,len1,s2,len2 -1,s3,len3 -1)

由于len3 === len1 + len2，所以这个问题里面实际上存在着两个变量，是一个二维动态规划题目。

从矩阵的角度来看的话，每一个元素的值，依赖于它的上边和左边两个值。

ref:

http:http://blog.unieagle.net/2012/09/29/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Ainterleaving-string%EF%BC%8C%E4%BA%8C%E7%BB%B4%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/

DP

Let F(i, j) denote if s1 of length i and s2 of length j could form s3 of lenght i+j, then we have four cases:

(1) F(i, j) = F(i-1, j) if s1[i-1] == s3[i+j-1] && s2[j-1] != s3[i +j -1]

(2) F(i, j) = F(i, j-1) if s1[i-1] != s3[i+j-1] && s2[j-1] == s3[i +j -1]

(3) F(i, j) = F(i-1, j) || F(i, j-1) if s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i +j -1]

(4) F(i, j) = false if s1[i-1] != s3[i+j-1] && s2[j-1] != s3[i +j -1]

但是merge sort没法考虑两个字符串的组合顺序问题。当处理{"C","CA", "CAC"}的时候，就不行了。



最后还是得用DP。对于

s1 = a1, a2 ........a(i-1), ai

s2 = b1, b2, .......b(j-1), bj

s3 = c1, c3, .......c(i+j-1), c(i+j)

定义 match[i][j] 意味着，S1的(0, i)和S2的(0,j)，匹配与S3的(i+j)

如果 ai == c(i+j), 那么 match[i][j] = match[i-1][j]， 等价于如下字符串是否匹配。



s1 = a1, a2 ........a(i-1)

s2 = b1, b2, .......b(j-1), bj

s3 = c1, c3, .......c(i+j-1)



同理，如果bj = c(i+j), 那么match[i][j] = match[i][j-1];



所以，转移方程如下：

Match[i][j]
    =   (s3.lastChar == s1.lastChar) && Match[i-1][j]
      ||(s3.lastChar == s2.lastChar) && Match[i][j-1]
初始条件：
    i=0 && j=0时，Match[0][0] = true;
    i=0时， s3[j] = s2[j], Match[0][j] |= Match[0][j-1]
           s3[j] != s2[j], Match[0][j] = false;

    j=0时， s3[i] = s1[i], Match[i][0] |= Match[i-1][0]
           s3[i] != s1[i], Match[i][0] = false;

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

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

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

        //initialization the first row and the first column
        int i = 1;
        while(i <= len1 && s1.charAt(i-1) == s3.charAt(i-1)){
            match[i][0]=true;
            i++;
        }

        int j = 1;
        while(j <= len2 && s2.charAt(j-1) == s3.charAt(j-1)){
            match[0][j] = true;
            j++;
        }

         //work through the rest of matrix using the formula
        for(int r = 1; r <= len1; r++){
            for(int c =1; c <= len2; c++){
                char s = s3.charAt(r+c-1);
                if(s == s1.charAt(r-1)){
                   match[r][c] = match[r][c] || match[r-1][c];
                }
                if(s == s2.charAt(c - 1)){
                     match[r][c] = match[r][c]|| match[r][c-1];
                }
            }
        }
        //the last element is the result
        return match[len1][len2];
    }
}

ref: http://www.cnblogs.com/feiling/p/3296057.html && http://fisherlei.blogspot.com/2012/12/leetcode-interleaving-string.html
原文链接: https://www.cnblogs.com/RazerLu/p/3535339.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍