題目

LeetCode - 97. Interleaving String

解題思路

題目要求判斷s3這個字串是否由s1及s2交錯組成，這題使用dp就可以解決了定義dp[i][j]: s3[0:i+j] 是不是由 s1[0:i] and s2[0:j]所組成

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m ,n ,l = len(s1),len(s2),len(s3)
        if m+n != l:
            return False
        ## dp[i][j]: s3[0:i+j] 是不是由 s1[0:i] and s2[0:j]所組成
        s1 = '#'+s1
        s2 = '#'+s2
        s3 = '#'+s3
        dp = [[ False for _ in range(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]==True and s1[i] == s3[i])
        for j in range(1, n+1):
            dp[0][j] = (dp[0][j-1]==True and s2[j] == s3[j])   
            
        for i in range(1, m+1):
            for j in range(1, n+1):
                if dp[i-1][j] == True and s1[i] == s3[i+j]:
                    dp[i][j] = True
                elif dp[i][j-1] == True and s2[j] == s3[i+j]:
                    dp[i][j] = True
        
        return dp[m][n]