(lintcode)第29题交叉字符串

交叉字符串

给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。

样例

比如 s1 = "aabcc" s2 = "dbbca"

- 当 s3 = "aadbbcbcac"，返回 true.

- 当 s3 = "aadbbbaccc"，返回 false.

思路：这道题一开始我是使用三个下标分别对应3个字符串，如果匹配上，那么就会往后移一位，但是这样就会有一个严重错误就是当s1=aabc,s2=aade,s3=aaddaabce,如果匹配上一位就后移，那么假设首先对s1匹配，那么直到aab的时候就会发现b这一位是没有办法匹配的，这时候和s2也没有办法匹配上，就会返回无法匹配，出现这个现象的原因是我写的代码没有考虑到回溯。

另一种思路是看别人的代码才想明白的，就是动态规划（DP），把一个大问题简化成为一个简单的问题，我们考虑长度为l1的s1，和长度为l2的s2能不能匹配成为长度为l1+l2的s3。

代码如下：

public class Solution {    /**     * Determine whether s3 is formed by interleaving of s1 and s2.     * @param s1, s2, s3: As description.     * @return: true or false.     */    public boolean isInterleave(String s1, String s2, String s3) {        if(null == s1 || null == s2 || null == s3 || s1.length() + s2.length() != s3.length())            return false;        if(s1.length() <= 0 && s2.length() <= 0 && s3.length() <= 0)            return true;        boolean[][] common = new boolean[s1.length() + 1][s2.length() + 1];        for(int i = 1;i <= s1.length();i++)        {            if(s1.charAt(i - 1) == s3.charAt(i - 1))            {                common[i][0] = true;            }        }        for(int i = 1;i <= s2.length();i++)        {            if(s2.charAt(i - 1) == s3.charAt(i - 1))            {                common[0][i] = true;            }        }        for(int i = 1;i <= s1.length();i++)        {            for(int j = 1;j <= s2.length();j++)            {                if(s1.charAt(i - 1) == s3.charAt(i + j - 1))                {                    common[i][j] = common[i - 1][j];                }                if(common[i][j])                {                    continue;                }                if(s2.charAt(j - 1) == s3.charAt(i + j - 1))                {                    common[i][j] = common[i][j - 1];                }            }        }        return common[s1.length()][s2.length()];    }}

如果有所帮助，脸皮厚求个赞~

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店

更多相关文章

随机推荐