---
# System prepended metadata

title: '**Leetcode筆記(Word Break)**'
tags: [值得再想, medium, dynamic programming, leetcode]

---

# **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://hackmd.io/_uploads/ByH4PSyw2.png)
![](https://hackmd.io/_uploads/Skc6Pr1w2.png)


**講解連結**
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` `值得再想`