LeetCode 139「单词拆分」要求判断字符串 s 能否被拆分成字典 wordDict 中的一个或多个单词（可重复使用）。
思路：动态规划
定义 dp[i] 表示 s 的前 i 个字符（即 s[0:i]）能否被成功拆分。
· 初始状态：dp[0] = True，空字符串默认可以拆分。
· 状态转移：对于每个位置 i，枚举分割点 j（0 ≤ 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_set=set(wordDict)n=len(s)dp=[False]*(n+1)dp[0]=Trueforiinrange(1,n+1):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_set=set(wordDict)memo={}defdfs(start:int)->bool:ifstart==len(s):returnTrueifstartinmemo:returnmemo[start]forendinrange(start+1,len(s)+1):ifs[start:end]inword_setanddfs(end):memo[start]=TruereturnTruememo[start]=FalsereturnFalsereturndfs(0)两种方法均可通过，动态规划更直观，DFS + 记忆化在字典单词长度较短时可能更快。
