?LeetCode刷題實戰(zhàn)97：交錯字符串
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?交錯字符串，我們先來看題面：
https://leetcode-cn.com/problems/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.
題意
解題
https://my.oschina.net/u/3640932/blog/4405751
狀態(tài)定義
dp[i][j]?表示 s1 前 i 個字符和 s2 前 j 個字符能夠拼接成 s3(i+j) 個字符，也就是當(dāng)前路徑存在。狀態(tài)轉(zhuǎn)移方程
dp[i][j]?是否成立，則需要看?dp[i-1][j]?是否成立，也就是這里需要看 s1 的前 i-1 個元素和 s2 的前 j 個元素能否拼接成 s3 的前 i+j-1 個元素。dp[i][j]?是否成立，則需要看?dp[i][j-1]?是否成立，也就是需要看 s2 的前 i 個元素和 s2 的前 j-1 個元素是否能夠拼接成 s3 的前 i+j-1 個元素。dp[i][j] = (dp[i-1][j] and s3[i+j-1]=s1[i-1]) or (dp[i][j-1] and s3[i+j-1]=s2[j-1])狀態(tài)初始化
dp[0][0] = True
如果 j = 0， dp[i][0] 是否成立，取決于 dp[i-1][0] 以及 s1 的第 i 個字符是否等于 s3 的第 i 個字符；
如果 i = 0， dp[0][j] 是否成立，取決于 dp[0][j-1] 以及 s3 的第 i 個字符與 s2 的第 i 個字符是否相等。
class Solution:
????def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
????????# 先處理特殊情況，如果 s1 和 s2 的長度和不等于 s3 的長度，則返回 False。因為無法交錯拼接
????????if?len(s1) + len(s2) != len(s3):
????????????return?False
????????
????????m?= len(s1)
????????n = len(s2)
????????# 狀態(tài)定義
????????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?s3[i-1] == s1[i-1]
????????for?j?in range(1, n+1):
????????????dp[0][j] = dp[0][j-1] and?s3[j-1] == s2[j-1]
????????for?i in range(1, m+1):
????????????for?j?in range(1, n+1):
????????????????dp[i][j] = (dp[i-1][j] and?s3[i+j-1]==s1[i-1]) or?(dp[i][j-1] and?s3[i+j-1]==s2[j-1])
????????return?dp[-1][-1]
上期推文：