单词拆分(一)

https://www.lintcode.com/problem/107/?utm_source=sc-libao-ql

描述

给定字符串 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做.

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]