LeetCode_动态规划_中等_97.交错字符串

待我称王封你为后i 2023-10-06 23:42 2阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

**给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。**

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：  
① s = s1 \+ s2 \+ … + sn  
② t = t1 \+ t2 \+ … + tm  
③ |n - m| <= 1  
④ 交错 是 s1 \+ t1 \+ s2 \+ t2 \+ s3 \+ t3 \+ … 或者 t1 \+ s1 \+ t2 \+ s2 \+ t3 \+ s3 \+ …  
注意：a + b 意味着字符串 a 和 b 连接。

**示例 1：**  
![在这里插入图片描述][28db42e7a56d4870953788cc341d1cdf.png]  
输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”  
输出：true

**示例 2：**  
输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”  
输出：false

**示例 3：**  
输入：s1 = “”, s2 = “”, s3 = “”  
输出：true

**提示：**  
0 <= s1.length, s2.length <= 100  
0 <= s3.length <= 200  
s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/interleaving-string

## 2.思路 ##

（1）动态规划  
思路参考[本题官方题解][Link 1]。

① 定义 dp 数组，dp\[i\]\[j\] = true 表示 s3 前 i + j 个字符由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成，否则则不能。

boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];

② 分析状态，当 dp\[i\]\[j\] 无非就两种情况：true 或 false。

③ 状态转移方程。显然 dp\[i\]\[j\] 的结果与 dp\[i - 1\]\[j\] 和 dp\[i\]\[j - 1\] 均有关：

1）如果 s1 的第 i 个元素和 s3 的第 i + j 个元素相等，那么 dp[i][j] 就取决于 dp[i - 1][j]；
    2）如果 s2 的第 j 个元素和 s3 的第 i + j 个元素相等，那么 dp[i][j] 就取决于 dp[i][j - 1]；

所以可以推导出状态转移方程如下：

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

## 3.代码实现（Java） ##

//思路1————动态规划
    class Solution {
        
        public boolean isInterleave(String s1, String s2, String s3) {
        
            int s1Len = s1.length();
            int s2Len = s2.length();
            int s3Len = s3.length();
            if (s1Len + s2Len != s3Len) {
        
                return false;
            }
            //dp[i][j] = true 表示 s3 前 i + j 个字符由 s1 的前 i 个字符和 s2 的前 j 个字符交错组成
            boolean[][] dp = new boolean[s1Len + 1][s2Len + 1];
            //边界条件
            dp[0][0] = true;
            // s1 和 s2 均有可能为空串，所以下标 i 和 j 均从 0 开始
            for (int i = 0; i <= s1Len; i++) {
        
                for (int j = 0; j <= s2Len; j++) {
        
                    int k = i + j - 1;
                    if (i > 0 && s1.charAt(i - 1) == s3.charAt(k)) {
         
                        dp[i][j] = dp[i - 1][j];
                    }
                    if (j > 0 && s2.charAt(j - 1) == s3.charAt(k)) {
        
                    	/*
                    		(1) | 与 || 在此处均可以，具体差别就在于后者是短路运算，不过对本题没有影响
    						(2) dp[i][j] |= dp[i][j - 1] 就等价于 dp[i][j] = dp[i][j] | dp[i][j - 1]
    						(3) 这里之所以要加上 |，其原因在于如果上面的 if 内的条件为 true 且 dp[i][j] 被设置为 true，而下面的 
    							dp[i][j - 1] 的结果为 false，在没有 | 的情况下，那么 dp[i][j] 会被错误地赋值为 false，这可能会
    							影响最终的结果，所以需要加上 | 来保证 dp[i][j] 不会被错误地赋值。
    					*/
                        dp[i][j] |= dp[i][j - 1];
                    }
                }
            }
            return dp[s1Len][s2Len];
        }
    }
    
    //由于数组 dp 的第 i 行至于第 i - 1 行有关，故可以使用滚动数组优化空间复杂度
    class Solution {
        
        public boolean isInterleave(String s1, String s2, String s3) {
        
            int s1Len = s1.length();
            int s2Len = s2.length();
            int s3Len = s3.length();
            if (s1Len + s2Len != s3Len) {
        
                return false;
            }
            boolean[] dp = new boolean[s2Len + 1];
            dp[0] = true;
            // s1 和 s2 均有可能为空串，所以下标 i 和 j 均从 0 开始
            for (int i = 0; i <= s1Len; i++) {
        
                for (int j = 0; j <= s2Len; j++) {
        
                    int k = i + j - 1;
                    if (i > 0) {
        
                        dp[j] &= s1.charAt(i - 1) == s3.charAt(k);
                    }
                    if (j > 0) {
        
                        dp[j] |= (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(k));
                    }
                }
            }
            return dp[s2Len];
        }
    }

[28db42e7a56d4870953788cc341d1cdf.png]: https://img-blog.csdnimg.cn/28db42e7a56d4870953788cc341d1cdf.png
[Link 1]: https://leetcode.cn/problems/interleaving-string/solution/jiao-cuo-zi-fu-chuan-by-leetcode-solution/