子寒的博客
0%

leetcode97 Interleaving String 解题报告

发表于 分类于

英文原题

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

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

s = s1 + s2 + … + sn t = t1 + t2 + … + tm |n - m| <= 1 The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + … or t1 + s1 + t2 + s2 + t3 + s3 + … Note: a + b is the concatenation of strings a and b.

Example example

分析

    又是一道动态规划，刚拿到题目我还没想到用动态规划，也是看了别人的思路才会做的。这是一道二维的动态规划，dp[i][j]表示s1前i个加上s2前j个是否可以组成s3的前i+j个。起初我在交错这个点上困住了，其实解法并不需要刻意去考虑交错的问题，因为其实两个字符串拆开排下来肯定是交错的。

python 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        len1 = len(s1)
        len2 = len(s2)
        len3 = len(s3)
        
        if len1 + len2 != len3:
            return False
        
        dp = [[False]*(len2+1) for _ in range(len1+1)]
        
        for i in range(len1+1):
            for j in range(len2+1):
                if i == 0 and j == 0:
                    dp[i][j] = True
                elif i == 0:
                    dp[i][j] = dp[i][j-1] and s2[j-1] == s3[j-1]
                elif j == 0:
                    dp[i][j] = dp[i-1][j] and s1[i-1] == s3[i-1]
                else:
                    dp[i][j] = (dp[i][j-1] and s2[j-1] == s3[i+j-1]) or (dp[i-1][j] and s1[i-1] == s3[i+j-1])
        
        return dp[len1][len2]