算法题--判断s3是否由s1和s2穿插而成

image.png

0. 链接

题目链接

1. 题目

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

2. 思路1: 动态规划

• 又是两个字符串的问题，第一时间想起动态规划
• 需要一个二维数组dp[i][j], i=0~m+1, j=0~n+1,
  其中i=0,j=0是凑数的,
  dp[i][j]表示s3的前i+j个字符，是否由s1的前i个字符和s2的前j个字符穿插而成.
• 初始条件

dp[0][0] = True

• 状态转移方程

i = 1~m
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

j = 1~n
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

i = 0~m-1, j=0~n-1
dp[i + 1][j + 1] = (dp[i][j + 1] and s1[i] == s3[i + j + 1]) or (dp[i + 1][j] and s2[j] == s3[i + j + 1])

3. 代码

# coding:utf8


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m = len(s1)
        n = len(s2)
        if len(s3) != m + n:
            return False

        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] and (s1[i - 1] == s3[i - 1])
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] and (s2[j - 1] == s3[j - 1])
        for i in range(m):
            for j in range(n):
                dp[i + 1][j + 1] = (dp[i][j + 1] and s1[i] == s3[i + j + 1]) \
                                or (dp[i + 1][j] and s2[j] == s3[i + j + 1])
        return dp[m][n]


def my_test(solution, s1, s2, s3):
    print('input: s1={}, s2={}, s3={}; output: {}'.format(
        s1, s2, s3, solution.isInterleave(s1, s2, s3)))


solution = Solution()
my_test(solution, 'aabcc', 'dbbca', 'aadbbcbcac')
my_test(solution, 'aabcc', 'dbbca', 'aadbbbaccc')
my_test(solution, "db", "b", "cbb")

输出结果

input: s1=aabcc, s2=dbbca, s3=aadbbcbcac; output: True
input: s1=aabcc, s2=dbbca, s3=aadbbbaccc; output: False
input: s1=db, s2=b, s3=cbb; output: False

结果

image.png