某途员工爆料：开始大规模裁员，预计比例40%-60%，聊完立马卷铺盖走人，没有交接没有过渡期~
P
虎哥约 3 分钟
虎哥约 3 分钟算法题：单词拆分
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
breakreturn 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高级架构师资料合集》。