139. 單詞拆分
-
給你一個字符串 s 和一個字符串列表 wordDict 作為字典。如果可以利用字典中出現的一個或多個單詞拼接出 s 則返回 true。
-
注意：不要求字典中出現的單詞全部都使用，并且字典中的單詞可以重復使用。
-
思路:
- 定義狀態：
-
設dp[i]表示字符串s的前 i 個字符（即 s[0:i]）
-
需計算 dp[len(s)]，即整個字符串 s 是否可以被拼接
- 狀態轉移方程：
-
對于每個位置i，需要檢查所有可能的分割點 j（0 <= j < i），檢查 s[j:i] 是否在字典中，并且 dp[j] 是否為 true
-
如果存在這樣的j，則 dp[i] = true
class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""# 將字典轉換為集合，方便快速查找wordSet = set(wordDict)n = len(s)dp = [False] * (n + 1)# 創建n+1個值全為False的數組dpdp[0] = True # 空字符串可以被拼接for i in range(1, n + 1): # 遍歷所有可能的結束位置for j in range(i): # 遍歷所有可能的分割點if dp[j] and s[j:i] in wordSet: # 如果s[j:i]在字典中，且dp[j] 為truedp[i] = Truebreak # 找到一個有效的分割點即可return dp[n]
- 時間復雜度: O(n^2)
- 空間復雜度: O(n)
)
