97. 交错字符串

题目链接:https://leetcode-cn.com/problems/interleaving-string/

题目描述:

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

思考:

这道题可以采用动态规划去解决,通过列举观察可以得出状态转移方程伪代码:

if(s1[i] == s3[i + j]){
  f[i][j] = f[i-1][j] 
}
if(s2[i] == s3[i + j]){
  f[i][j]=f[i][j-1] 
}

踩到的坑:

开始想着用递归方式去解决,可无奈时间复杂度太高,提交后显示超时,不得不采用前溯去处理。

实现:

递归实现:

public static boolean isInterleave(String s1, String s2, String s3) {
        if ((s1.length() + s2.length()) != s3.length()) {
            return false;
        }
        if (s1.length() == 0 && s2.length() == 0){
            return true;
        }
        if (s1.length() == 0 || s2.length() == 0){
            if (s3.equals(s1 + s2)){
                return true;
            } else {
                return false;
            }
        }
        Boolean condiction1 = s1.substring(s1.length() - 1).equals(s3.substring(s3.length()-1));
        Boolean condiction2= s2.substring(s2.length() - 1).equals(s3.substring(s3.length()-1));
        if (condiction2 && condiction1){
            if (isInterleave(s1, s2.substring(0, s2.length() - 1), s3.substring(0, s3.length()-1)) || isInterleave(s1.substring(0, s1.length() - 1), s2, s3.substring(0, s3.length()-1))){
                return true;
            } else {
                return false;
            }
        } else if(condiction1 && !condiction2){
            return isInterleave(s1.substring(0, s1.length() - 1), s2, s3.substring(0, s3.length()-1));
        } else if(!condiction1 && condiction2){
            return isInterleave(s1, s2.substring(0, s2.length() - 1), s3.substring(0, s3.length()-1));
        }
        return false;
    }

非递归实现:

 public static boolean isInterleave0(String s1, String s2, String s3){
        int m = s1.length();
        int n = s2.length();
        int s = s3.length();
        if ((m + n) != s){
            return false;
        }
        boolean[][] f = new boolean[m+1][n+1];
        f[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0){
                    f[i][j] = f[i][j] || ((f[i - 1][j] && (s1.charAt(i-1) == s3.charAt(i + j - 1))));
                }
                if (j > 0){
                    f[i][j] = f[i][j] || ((f[i][j - 1] && (s2.charAt(j-1) == s3.charAt(i + j - 1))));
                }
            }
        }
        return f[m][n];
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容