算法题:单词拆分
s
和一个单词字典 wordDict
,问你能不能把 s
分割成字典里的单词序列。要求每个单词都必须在字典里,不许编造新词。这听着像我上学时用拼音写作文:一个个词瞎拼,最后老师批我“这是什么火星文?”s = "leetcode"
wordDict = ["leet", "code"]
# 输出: True,因为 "leetcode" 可以拆成 "leet" 和 "code"。
问题拆解
aaaaaaaaaa...aaa
,而字典里只有 a
和 aa
,暴力法基本可以直接劝退面试官,让他回家反思题目是不是太难了。dp
,dp[i]
表示字符串前 i
个字符能否用字典里的单词拼出来。dp[i] = True
当且仅当存在一个 j
,使得 dp[j] == True
且 s[j:i]
在 wordDict
中。动态规划代码
def wordBreak(s, wordDict):
wordSet = set(wordDict) # 用集合加速查找
dp = [False] * (len(s) + 1)
dp[0] = True # 空字符串能被拆分
for i in range(1, len(s) + 1):
for j in range(i):
# 检查从j到i的子串是否在字典中,同时之前的状态也得是True
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
return dp[-1]
# 测试一下
s = "applepenapple"
wordDict = ["apple", "pen"]
print(wordBreak(s, wordDict)) # 输出: True
一些优化点
字典查找效率:用 set
存储wordDict
,查询复杂度从 O(n) 降到 O(1)。这优化就像我把平时乱扔的文件都丢进一个文件夹,查找起来贼快。子串切割:DP 里的双层循环是必要的,但如果字典里单词长度有限,可以稍微剪枝,只考虑长度范围内的切割。
maxWordLen = max(map(len, wordDict)) # 字典里最长单词长度
for i in range(1, len(s) + 1):
for j in range(max(0, i - maxWordLen), i): # 优化切割范围
if dp[j] and s[j:i] in wordSet:
dp[i] = True
break
特别提醒
set
的用法,甚至是 max()
这种基础函数,用得巧妙就能少写不少代码。对编程、职场感兴趣的同学,大家可以联系我微信:golang404,拉你进入“程序员交流群”。
虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》。