# **Leetcode筆記(Word Break)**
:::info
:information_source: 題目 : Word Break, 類型 : dynamic programming , 等級 : medium
日期 : 2023/02/25，2023/06/08，2023/07/19，2023/10/24，2024/02/20
:::
### 嘗試
思路算相同，但是在if的部分內部不知道操作
```python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
i = 0
while i < len(s):
for j in range(len(wordDict)):
lengthW = len(wordDict[j])
newS = s[i : i + lengthW]
if newS == wordDict[j]:
i += lengthW
return True
else:
return False
break
```
2023/06/08
範例s = "catsandog"
wordDict = ["cats","dog","sand","and","cat"]
每個一一去對照(每一個word都要跑)(第一個位置初始化為T)，
會是
**catsandog
TFFTTFFTFF**
最後只要看最後一個是T還是F
(記得如果[0:3]有字是符合的，True是標在[4])
```python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
# 初始化
dp[0] = True
for i in range(len(s)):
if dp[i]:
for w in wordDict:
if w == s[i : i + len(w)]:
dp[i + len(w)] = True
return dp[-1]
```
2023/07/19
從第一個字開始尋找，**如果有word跟它有所對應，就把dp[i + len(word)]那邊設為True**
注意前面要有dp[i] = True才可以進去
初始化要把i = 0設為True
```python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(len(s)):
if dp[i]:
for word in wordDict:
if s[i : i + len(word)] == word:
dp[i + len(word)] = True
return dp[len(s)]
```
2023/10/24
一定要i在外面的loop，w在裡面的，因為w可以重複使用
```python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
record = [False] * (len(s) + 1)
record[0] = True
for i in range(len(s)):
for w in wordDict:
wLen = len(w)
if record[i] and s[i : i + wLen] == w:
record[i + wLen] = True
return record[len(s)]
```
2024/02/20
```python
class Solution(object):
def wordBreak(self, s, wordDict):
record = [False] * (len(s) + 1)
record[0] = True
for i, c in enumerate(s):
for w in wordDict:
wlen = len(w)
if i + wlen <= len(s) and w == s[i : i + wlen] and record[i]:
record[i + wlen] = True
return record[len(s)]
```
---
### **優化**
常用樹狀圖下去思考，有甚麼重複的步驟，例如這裡重複的步驟就是一直需要選擇不一樣的wordDict去測。
可以先初始化list，因為輸出是bool所以用bool初始化，最後利用該list輸出，基本上用倒敘去想，if內部經常是短短的一句指派。
時間複雜度O(nm)，空間複雜度O(n)
```python
# 若資測為s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
# 則到n處就會一直是False -> 如果在中間找不到相對應的資測就會一直False下去
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[len(s)] = True # 多一格給它初始化為True
for i in reversed(range(len(s))):
for j in range(len(wordDict)):
Wlength = len(wordDict[j])
if s[i : i + Wlength] == wordDict[j]: # 若字串相同
# 講解有加這個條件(但非必要)i + Wlength <= len(s) and
# 此條件的=是給第一次w與s配對 之後每次都會符合小於這個條件
dp[i] = dp[i + Wlength]
if dp[i] == True:
# 要馬上跳出去找下一個 不然會有重複配對的問題
# 如s = "abcd", wordDict = ["a","abc","b","cd"]會重複配對到c
break
return dp[0]
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
初始化dp = [False] * (len(s) + 1)
字串擷取部分s[i : i + Wlength]
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=Sx9NNgInc3A
https://www.youtube.com/watch?v=bbjD_AfQZyU&t=1134s&ab_channel=%E4%BB%8A%E5%A4%A9%E6%AF%94%E6%98%A8%E5%A4%A9%E5%8E%B2%E5%AE%B3
Provided by. NeetCode & 今天比昨天厲害
###### tags: `dynamic programming` `medium` `leetcode` `值得再想`
Sign in with Wallet
Connect another wallet