LeetCode热题100-单词拆分

给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

核心思路（动态规划）

• 定义dp[i]：前 i 个字符能否被拆分
• 初始化：dp[0] = True（空串合法）
• 转移：对每个位置i，往前找一个j，如果dp[j]合法，并且s[j:i]在字典里→dp[i] = True

至于为什么长度是n + 1而不是n，原因：

dp [i] 表示：字符串前 i 个字符能否拆分

• 字符串下标是0 ~ n-1
• 前 0 个字符：空串
• 前 1 个字符：s [0]
• 前 2 个字符：s [0] s [1]
• ...
• 前n 个字符：整个字符串 s [0..n-1]

所以要想表示整个字符串，dp 必须开到dp[n]

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: word_set = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in word_set: dp[i] = True return dp[n]