97、交错字符串

leetcode

Created At : 2020-07-26 00:19

Count:1.5k Views 👀 :

Comment:

示例 1:
示例 2:

思路

1、递归匹配
2、动态规划

代码

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

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

思路

1、递归匹配

简单回溯
记忆化回溯
- 这种冗余可以通过在回溯的过程中使用记忆化去除。为了达到这个目的，我们维护 3 个指针 i, j, k ，分别指向 s1, s2, s3当前位置。同时，我们维护一个 2D 的记忆数组，记录目前已经处理过的子字符串。 memo[i][j] 保存的值是 1/0 或者 -1 ，取决于状态，也就是 s1 下标为
  $$i^{th} $$
  且 s2 下标为
  $$ j^{th} $$
  是否已经被处理过。与方法 1 类似，我们通过判断 s1 的当前字符（通过指针 i 表示）与 s3 的当前字符（通过指针 k 来表示），如果相等，我们可以将它放到暂存的结果串中，并同样递归调用函数：
  $$ is_Interleave(s1,i+1,s2,j,s3,k+1,memo) $$

2、动态规划

二维动态规划：使用s1和s2的某个前缀是否能形成s3的一个前缀
- 前提：判断一个 s3 的前缀（用下标 k 表示），能否用 s1 和 s2 的前缀（下标分别为 i 和 j），仅仅依赖于 s1 前 i 个字符和 s2 前 j 个字符，而与后面的字符无关。
- dp[i][j] 表示用s1的前（i+1）和s2的前（j+1）个字符，总共（i+j+2）个字符，是否交错构成s3前缀。因此，dp[i][j]初始化为false.下面是递推公式
- dp[i][j] = false <== s1[i] != s3[k] && s2[j] != s3[k] (k = i+j+1)
- dp[i][j] = dp[i-1][j] & dp[i][j-1] &(s1[i] == s3[k] || s2[j] == s3[k]) (k=i+j+1)
一维动态规划
- 都是注意到一个特点，当更新到 dp [ i ] [ j ] 的时候，我们只用到 dp [ i - 1 ] [ j ] ，即上一层的数据，再之前的数据就没有用了。所以我们不需要二维数组，只需要一个一维数组就够了。
- 利用 dp[i-1] 的结果和 dp[i] 之前的结果来计算 dp[i] ，即滚动数组。

代码

递归、回溯

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true;
        if (s3 == null || s3.length() == 0) return false;
        if (s3.length() != (s1.length() + s2.length())) return false;
        return isInterleaveCore(s1,0,s2,0,s3,0);
    }
    
    private boolean isInterleaveCore(String s1,int i,String s2,int j,String s3,int k) {
        if ((i+j) == k && k == s3.length()) return true;
        if (i < s1.length() && j < s2.length()) {
            return s1.charAt(i) == s3.charAt(k) && isInterleaveCore(s1,i+1,s2,j,s3,k+1) || s2.charAt(j) == s3.charAt(k) && isInterleaveCore(s1,i,s2,j+1,s3,k+1);
        } else if (i < s1.length() && s1.charAt(i) == s3.charAt(k)){
            return isInterleaveCore(s1,i+1,s2,j,s3,k+1);
        } else if (j < s2.length() && s2.charAt(j) == s3.charAt(k)) {
            return isInterleaveCore(s1,i,s2,j+1,s3,k+1);
        }
        return false; 
    }
}
// 枚举全部情况，进行字符串匹配
public class Solution{
    public boolean isInterleaveCore(String s1,int i,String s2,int j,String res,String s3) {
        // 递归结束
        if (res.equals(s3) && i == s1.length() && j == s2.length());
            return true;
        boolean ans = false;
        if (i < s1.length()) {
            ans |= isInterleaveCore(s1,i+1,s2,j,res+s1.charAt(i),s3);
        }
        if (j < s2.length()) {
            ans |= isInterleaveCore(s1,i,s2,j+1,res+s2.charAt(j),s3);
        }
        return ans;
    }

    public boolean isInterleave(String s1,String s2,String s3) {
        return isInterleaveCore(s1,0,s2,0,"",s3);
    }
}

记忆化回溯

class Solution {
       public boolean is_Interleave(String s1, int i, String s2, int j, String s3, int k, int[][] memo) {
        // s1 字符串匹配结束
       if (i == s1.length()) {
           return s2.substring(j).equals(s3.substring(k));
       }
       // s2字符串匹配结束
       if (j == s2.length()) {
           return s1.substring(i).equals(s3.substring(k));
       }
       // s1[i]、s2[j]已经被处理完毕，直接返回。不用再重复递归计算
       if (memo[i][j] >= 0) {
           return memo[i][j] == 1 ? true : false;
       }
       boolean ans = false;
       // 满足条件则递归，或的关系
       if (s3.charAt(k) == s1.charAt(i) && is_Interleave(s1, i + 1, s2, j, s3, k + 1, memo)
               || s3.charAt(k) == s2.charAt(j) && is_Interleave(s1, i, s2, j + 1, s3, k + 1, memo)) {
           ans = true;
       // 更新状态
       memo[i][j] = ans ? 1 : 0;
       return ans;
   }
   public boolean isInterleave(String s1, String s2, String s3) {
       int memo[][] = new int[s1.length()][s2.length()];
       // 初始化状态
       for (int i = 0; i < s1.length(); i++) {
           for (int j = 0; j < s2.length(); j++) {
               memo[i][j] = -1;
           }
       }
       return is_Interleave(s1, 0, s2, 0, s3, 0, memo);
   }

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/interleaving-string/solution/jiao-cuo-zi-fu-chuan-by-leetcode/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}

二维动态规划

public boolean isInterleave(String s1,String s2,String s3) {
    // 长度不匹配
    if (s3.length() != s2.length() + s1.length()) return false;
    boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
    for (int i = 0;i < s1.length(); i++) {
        for (int j = 0;j < s2.length(); j++) {
            if (i == 0 && j == 0) {
                dp[i][j] = true;
            } else if (i == 0) {
                dp[i][j] = dp[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(i+j-1));
            } else if (j == 0) {
                dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i+j-1);
            } else {
                dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i+j-1)) ||
                (dp[i][j - 1] && (s2.charAt(j-1) == s3.charAt(i+j-1)));
            }
        }
    }
    return dp[s1.length()][s2.length()];
}

一维动态规划

public boolean isInterleave(String s1,String s2,String s3) {
    // 长度不匹配
    if (s3.length() != s2.length() + s1.length()) return false;
    // 滚动数组，数组复用
    boolean[] dp = new boolean[s2.length() + 1];
    for (int i = 0;i <= s1.length(); i++) {
        for (int j = 0;j <= s2.length(); j++) {
            if (i == 0 && j == 0) {
                dp[j] = true;
            } else if (i == 0) {
                dp[j] = dp[j - 1] && (s2.charAt(j - 1) == s3.charAt(i+j-1));
            } else if (j == 0) {
                dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i+j-1);
            } else {
                dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i+j-1)) ||
                (dp[j - 1] && (s2.charAt(j - 1) == s3.charAt(i+j-1)));
            }
        }
    }
    return [s2.length()];
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com