097 Interleaving String 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
例如，
给定：
s1 = "aabcc",
s2 = "dbbca",
当 s3 = "aadbbcbcac", 返回 true.
当 s3 = "aadbbbaccc", 返回 false.
详见：https://leetcode.com/problems/interleaving-string/description/

Ø d b b c a
Ø T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T

字符串s1和s2的长度和必须等于s3的长度，如果不等于，肯定返回false。那么当s1和s2是空串的时候，s3必然是空串，则返回true。所以直接给dp[0][0]赋值true，然后若s1和s2其中的一个为空串的话，那么另一个肯定和s3的长度相等，则按位比较，若相同且上一个位置为True，赋True，其余情况都赋False，这样的二维数组dp的边缘就初始化好了。在任意非边缘位置dp[i][j]时，它的左边或上边有可能为True或是False，两边都可以更新过来，只要有一条路通着，那么这个点就可以为True。那么分别来看，如果左边的为True，那么去除当前对应的s2中的字符串s2[j - 1] 和 s3中对应的位置的字符相比（计算对应位置时还要考虑已匹配的s1中的字符），为s3[j - 1 + i], 如果相等，则赋True，反之赋False。而上边为True的情况也类似，所以可以求出递推公式为：
dp[i][j] = (dp[i - 1][j] && s1[i - 1] == s3[i - 1 + j]) || (dp[i][j - 1] && s2[j - 1] == s3[j - 1 + i]);
其中dp[i][j] 表示的是 s2 的前 i 个字符和 s1 的前 j 个字符是否匹配 s3 的前 i+j 个字符。

Java实现：

class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {

        int m=s1.length();

        int n=s2.length();

        if(m+n!=s3.length()){

            return false;

        }

        boolean[][] path=new boolean[m+1][n+1];

        for(int i=0;i<m+1;++i){

            for(int j=0;j<n+1;++j){

                if(i==0&&j==0){

                    path[i][j]=true;

                }else if(i==0){

                    path[i][j]=path[i][j-1]&&(s2.charAt(j-1)==s3.charAt(j-1));

                }else if(j==0){

                    path[i][j]=path[i-1][j]&&(s1.charAt(i-1)==s3.charAt(i-1));

                }else{

                    path[i][j] = (path[i][j-1] && (s2.charAt(j-1)==s3.charAt(i+j-1)))

                              || (path[i-1][j] && (s1.charAt(i-1)==s3.charAt(i+j-1)));

                }

            }

        }

        return path[m][n];

    }

}

参考：https://www.cnblogs.com/grandyang/p/4298664.html

巴特西

097 Interleaving String 交错字符串

最新文章

热门文章