> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2024/dan-ci-chai-fen-yi.md).

# 单词拆分(一)

描述

给定字符串 `s` 和单词字典 `dict`，判断是否可以利用字典 `dict` 中的出现的单词拼接出 `s`，其中字典 `dict` 中的单词可以重复使用。

因为我们已经使用了更强大的数据，所以普通的DFS方法无法解决此题。

$$s.length<=1e5s.length<=1e5$$\
$$dict.size<=1e5dict.size<=1e5$$

样例

**样例 1：**

输入：

```
s = "lintcode"dict = ["lint", "code"]
```

输出：

```
true
```

解释：

lintcode可以分成lint和code。

**样例 2：**\
\
输入：

```
s = "a"dict = ["a"]
```

输出：

```
true
```

解释：

a在dict中。

**分析**： 解题思路

**解题思路**：

该题目是一个典型的动态规划问题，旨在判断一个字符串 `s` 是否可以拆分成字典中的单词组合。通过设置一个 `dp` 数组，我们可以逐步判断每个子串是否能够在字典中找到。

1. 初始化 `dp` 数组，`dp[i]` 表示字符串前 `i` 个字符能否被字典中的单词组合拆分。
2. 设置 `dp[0]` 为 `True`，表示空字符串可以被完全拆分。
3. 遍历字符串的每个字符，并检查从当前字符向前 `max_len` 长度的字串是否在字典中。
4. 如果某个子串存在于字典中且之前的状态 `dp[j]` 为 `True`，则更新当前状态 `dp[i]` 为 `True`。
5. 最终返回 `dp[n]`，表示整个字符串是否可以被拆分成字典中的单词组合。

也可以用dfs+memo做.

````python
from typing import (
    Set,
)

class Solution:
    """
    @param s: A string
    @param word_set: A dictionary of words dict
    @return: A boolean
    """
    def word_break(self, s: str, word_set: Set[str]) -> bool:
        # write your code here
        if not s:
            return True
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        max_len = max((len(word) for word in word_set), default=0) #注意字典为空 需要有默认值0
        for i in range(1, n+1):
            for j in range(max(0, i - max_len), i):#最长的词开始遍历 而不是每个字母都遍历，否则超时
                if dp[j] and s[j:i] in word_set:
                    print(s[j:i])
                    dp[i] = True
                    break
        #换成长度遍历更好想
        ```python
        for i in range(1, n+1):
            for l in range(0, max_len+1):#最长的词开始遍历 而不是每个字母都遍历，否则超时
                if dp[i-l] and s[i-l:i] in word_set:
                    dp[i] = True
                    break
        ```
        return dp[n]

````