双序列型动态规划——交错字符串

梦里梦外; 2022-10-27 12:07 220阅读 0赞

#  #

给定三个字符串 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：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

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

### 1、确定状态 ###

如果X的长度不等于A的长度+B的长度，直接输出False

设A长度是m, B长度是n，X的长度是m+n

最后一步：假设X是由A和B交错形成的，那么X的最后一个字符X\[m+n-1\]

– 要么是A\[m-1\]

• 那么X\[0…m+n-2\]是由A\[0…m-2\]和B\[0…n-1\]交错形成的

– 要么是B\[n-1\]

• 那么X\[0…m+n-2\]是由A\[0…m-1\]和B\[0…n-2\]交错形成的

因此，要求X\[0…m+n-1\]是否由A\[0…m-1\]和B\[0…n-1\]交错形成。需要知道X\[0…m+n-2\]是否由A\[0…m-2\]和B\[0…n-1\]交错形成，以及 X\[0…m+n-2\]是否由A\[0…m-1\]和B\[0…n-2\]交错形成。

因此可以假设状态f\[i\]\[j\]为X前i+j个字符是否由A前i个字符 A\[0…i-1\]和B前j个字符B\[0…j-1\]交错形成

### 2、转移方程 ###

设f\[i\]\[j\]为X前i+j个字符是否由A前i个字符A\[0…i-1\]和B前j个字符B\[0…j-1\]交错 形成  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]

### 3、初始条件和边界情况 ###

初始条件：空串由A的空串和B的空串交错形成f\[0\]\[0\] = True

边界情况：如果i=0，不考虑情况一；如果j=0，不考虑情况二

### 4、计算顺序 ###

逐行计算，答案是f\[m\]\[n\]

时间复杂度：O(MN)，空间复杂度：O(MN)

### 5、代码实现 ###

class Solution(object):
        def isInterleave(self, s1, s2, s3):
            """ :type s1: str :type s2: str :type s3: str :rtype: bool """
            if len(s1) + len(s2) != len(s3):
                return False
            n = len(s1) + 1
            m = len(s2) + 1
            dp = [[False] * m for i in range(n)]
            for i in range(n):
                for j in range(m):
                  	if i==0 and j==0:
                      dp[i][j]=True
                      continue
                    if i > 0 and s1[i - 1] == s3[i + j - 1]:
                        dp[i][j] = dp[i - 1][j]
                    if j > 0 and s2[j - 1] == s3[i + j - 1]:
                        dp[i][j] = dp[i][j] or dp[i][j - 1]
            return dp[n - 1][m - 1]

#  #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/a9ed26fb69e540a7890dd8d437acf744.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]: /images/20221024/f86c5c9148864c7eb73401349b6aa710.png