LeetCode热题100-单词拆分

张开发
• 2026/4/21 3:17:19 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

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]

更多文章