DeepSeek LeetCode 139.单词拆分 Python3实现

LeetCode 139「单词拆分」要求判断字符串 s 能否被拆分成字典 wordDict 中的一个或多个单词可重复使用。思路动态规划定义 dp[i] 表示 s 的前 i 个字符即 s[0:i]能否被成功拆分。· 初始状态dp[0] True空字符串默认可以拆分。· 状态转移对于每个位置 i枚举分割点 j0 ≤ j i若 dp[j] True 且 s[j:i] 在字典中则 dp[i] True。· 最终答案dp[n]其中 n len(s)。为了快速判断子串是否在字典中将 wordDict 转为 set。Python3 实现fromtypingimportListclassSolution:defwordBreak(self,s:str,wordDict:List[str])-bool:word_setset(wordDict)nlen(s)dp[False]*(n1)dp[0]Trueforiinrange(1,n1):forjinrange(i):ifdp[j]ands[j:i]inword_set:dp[i]Truebreakreturndp[n]复杂度分析指标 值时间复杂度 O(n²)其中 n 为字符串长度每次子串判断 s[j:i] in set 平均 O(1)空间复杂度 O(n)用于 dp 数组和哈希集合补充记忆化 DFS另一种常见写法fromtypingimportListclassSolution:defwordBreak(self,s:str,wordDict:List[str])-bool:word_setset(wordDict)memo{}defdfs(start:int)-bool:ifstartlen(s):returnTrueifstartinmemo:returnmemo[start]forendinrange(start1,len(s)1):ifs[start:end]inword_setanddfs(end):memo[start]TruereturnTruememo[start]FalsereturnFalsereturndfs(0)两种方法均可通过动态规划更直观DFS 记忆化在字典单词长度较短时可能更快。