【LeetCode刷题】单词拆分

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

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

示例 1：

输入:s = "leetcode", wordDict = ["leet", "code"]输出:true解释:返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入:s = "applepenapple", wordDict = ["apple", "pen"]输出:true解释:返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入:s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出:false

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s和wordDict[i]仅由小写英文字母组成
• wordDict中的所有字符串互不相同

解题思路（动态规划）

1. 定义状态：设dp[i]表示 “字符串s的前i个字符是否能被字典中的单词拼接而成”。
2. 初始化：dp[0] = True（空字符串默认可以被拆分）；其余dp[i]初始化为False。
3. 状态转移：
   • 遍历字符串的每个位置i（从 1 到len(s)）；
   • 对每个单词word，若i ≥ len(word)且dp[i - len(word)]为True，同时s[i - len(word):i] == word，则将dp[i]设为True。
4. 结果：最终返回dp[len(s)]（表示整个字符串是否能被拆分）。

Python代码：

from typing import List class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: """ 字符串拆分问题：判断字符串能否被字典中的单词拼接而成（单词可重复使用） :param s: 待拆分的目标字符串（非空/空字符串均可） :param wordDict: 单词字典列表（元素为非空字符串） :return: 布尔值，True表示可拆分，False表示不可拆分 """ # 边界条件1：空字符串默认可拆分（题目隐含规则） if not s: return True # 边界条件2：字典为空，且字符串非空 → 无法拆分 if not wordDict: return False # 优化1：转集合提升单词查找效率（O(1)） word_set = set(wordDict) # 优化2：统计字典中单词的最大长度，减少无效子串遍历 max_word_len = max(len(word) for word in wordDict) n = len(s) # dp[i] 表示s的前i个字符（s[0:i]）能否被字典单词拆分 dp = [False] * (n + 1) dp[0] = True # 基准条件：空字符串可拆分 # 遍历字符串每个位置i（表示前i个字符） for i in range(1, n + 1): # 优化：仅遍历 i - max_word_len 到 i 的范围（超出字典单词长度的子串无需检查） start = max(0, i - max_word_len) for j in range(start, i): # 条件：前j个字符可拆分 + 子串s[j:i]在字典中 if dp[j] and s[j:i] in word_set: dp[i] = True break # 找到有效匹配，无需继续遍历 return dp[n] # ------------------- 测试用例 ------------------- if __name__ == "__main__": solution = Solution() # 测试用例1：常规可拆分（题目示例1） s1 = "leetcode" wordDict1 = ["leet", "code"] print(f"测试用例1：s='{s1}', wordDict={wordDict1}") print(f"是否可拆分：{solution.wordBreak(s1, wordDict1)}") # 预期输出：True # 测试用例2：可拆分（单词重复使用） s2 = "applepenapple" wordDict2 = ["apple", "pen"] print(f"\n测试用例2：s='{s2}', wordDict={wordDict2}") print(f"是否可拆分：{solution.wordBreak(s2, wordDict2)}") # 预期输出：True # 测试用例3：不可拆分（题目示例3） s3 = "catsandog" wordDict3 = ["cats", "dog", "sand", "and", "cat"] print(f"\n测试用例3：s='{s3}', wordDict={wordDict3}") print(f"是否可拆分：{solution.wordBreak(s3, wordDict3)}") # 预期输出：False # 测试用例4：边界场景 - 空字符串 s4 = "" wordDict4 = ["a", "b"] print(f"\n测试用例4：s='{s4}', wordDict={wordDict4}") print(f"是否可拆分：{solution.wordBreak(s4, wordDict4)}") # 预期输出：True # 测试用例5：边界场景 - 字典无匹配单词 s5 = "hello" wordDict5 = ["hi", "world"] print(f"\n测试用例5：s='{s5}', wordDict={wordDict5}") print(f"是否可拆分：{solution.wordBreak(s5, wordDict5)}") # 预期输出：False

LeetCode提交代码：

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: # 将字典转为集合，优化查找效率 word_set = set(wordDict) n = len(s) # dp[i]表示s的前i个字符能否被拆分 dp = [False] * (n + 1) dp[0] = True # 空字符串默认可拆分 # 遍历每个位置i for i in range(1, n + 1): # 遍历每个单词，判断是否能匹配s的子串 for word in word_set: word_len = len(word) # 条件：当前位置i不小于单词长度 + 前i-word_len个字符可拆分 + 子串匹配单词 if i >= word_len and dp[i - word_len] and s[i - word_len:i] == word: dp[i] = True break # 找到一个有效匹配即可，无需继续遍历单词 return dp[n]

程序运行结果展示

测试用例1：s='leetcode', wordDict=['leet', 'code'] 是否可拆分：True 测试用例2：s='applepenapple', wordDict=['apple', 'pen'] 是否可拆分：True 测试用例3：s='catsandog', wordDict=['cats', 'dog', 'sand', 'and', 'cat'] 是否可拆分：False 测试用例4：s='', wordDict=['a', 'b'] 是否可拆分：True 测试用例5：s='hello', wordDict=['hi', 'world'] 是否可拆分：False

总结

本文介绍了一个字符串拆分问题，判断给定字符串s是否能由字典wordDict中的单词拼接而成（单词可重复使用）。采用动态规划解法，定义dp[i]表示s前i个字符能否被拆分，初始化dp[0]=True，通过遍历字符串位置和字典单词进行状态转移。Python实现中优化了字典查找效率，并处理了边界条件。测试用例验证了算法的正确性，包括常规可拆分、单词重复使用、不可拆分及空字符串等场景。最终返回dp[n]作为结果，时间复杂度为O(n*m)，其中n为字符串长度，m为字典单词数。