算法题

昨天晚上十一点多,我在公司楼下抽烟,我们组那个老李突然拦住我:哥,这道Word Break咋写啊,我脑壳疼。

我扫了一眼代码,心想这题挺经典的,来,我给你捋一捋。

##算法题：Word Break

题目理解

题目说给你一个字符串 s 和一个单词列表 wordDict。

你要判断 s 能不能被拆分成若干个 wordDict 里的单词。

拆分时可以重复使用字典中的单词。

举例说明:

• 输入 s="leetcode",wordDict=["leet","code"],输出 true。拆分成"leet"+"code"
• 输入 s="applepenapple",wordDict=["apple","pen"],输出 true。拆分成"apple"+"pen"+"apple"
• 输入 s="catsandog",wordDict=["cats","dog","sand","and","cat"],输出 false。无法拆分

说白了就是:把字符串切成几段,每段都要在字典里能找到。

思路分析

暴力解法:枚举所有可能的拆分方式,检查每种方式是否都在字典里。2^n种拆分方式,每段检查O(1)(用哈希表),时间复杂度 O(2^n)。n=100时直接爆。

优化思路 - 动态规划:用 dp[i] 表示 s[0:i] 能否被拆分。dp[0]=true(空字符串可以拆分)。对于每个位置i,遍历所有可能的分割点j,如果 dp[j]==true 且 s[j:i] 在字典里,则 dp[i]=true。时间复杂度 O(n²),空间复杂度 O(n)。n=10000时就是一亿次操作,可以接受。

核心思想是:如果前半部分能拆分,而且后半部分是字典里的词,那整个就能拆分。

复杂度分析

• 时间复杂度:O(n²),其中 n 是字符串长度
• 空间复杂度:O(n),dp数组的大小

代码实现

package main

import (
"fmt"
)

// wordBreak 判断字符串能否被拆分成字典中的单词
func wordBreak(s string, wordDict []string) bool {
// 将字典转为哈希集合,方便查找
 wordSet := make(map[string]bool)
for _, word := range wordDict {
  wordSet[word] = true
 }

 n := len(s)
 dp := make([]bool, n+1)
 dp[0] = true// 空字符串可以拆分

for i := 1; i <= n; i++ {
// 遍历所有可能的分割点j
for j := 0; j < i; j++ {
   // 如果前半部分能拆分,且后半部分在字典里
   if dp[j] && wordSet[s[j:i]] {
    dp[i] = true
    break// 找到一种拆分方式就行
   }
  }
 }

return dp[n]
}

func main() {
// 测试用例
 fmt.Println(wordBreak("leetcode", []string{"leet", "code"}))  // true
 fmt.Println(wordBreak("applepenapple", []string{"apple", "pen"}))  // true
 fmt.Println(wordBreak("catsandog", []string{"cats", "dog", "sand", "and", "cat"}))  // false
 fmt.Println(wordBreak("aaaaaaa", []string{"aaaa", "aa"}))  // true
 fmt.Println(wordBreak("", []string{"a"}))  // true
}

注意事项

• 字典预处理:先将 wordDict 转为哈希集合,这样查找单词就是 O(1)。如果不用哈希集合,每次查找是 O(m)(m是单词长度),总复杂度就变成 O(n²m)了。
• dp[0]=true:空字符串可以拆成0个单词,所以 dp[0]=true。这是边界条件,也是后续计算的基础。
• 找到一种拆分方式就行:如果 dp[j]=true 且 s[j:i] 在字典里,就说明 s[0:i] 能拆分,可以 break,不用继续遍历其他分割点。
• 重复使用单词:题目说可以重复使用字典中的单词,所以 dp[j] 只要为 true 就行,不需要考虑单词是否用过了。
• 字符串切片:Go中 s[j:i] 是左闭右开的,所以 dp[i] 对应的是 s[0:i]。要注意索引范围,j 从 0 到 i-1。
• 空字符串:如果 s 是空字符串,空字符串可以拆成0个单词,直接返回 true。

这题的关键点在于理解动态规划的状态转移。dp[i] 表示前 i 个字符能否拆分,如果某个位置 j 之前能拆分,而且 s[j:i] 是字典里的词,那 dp[i] 就能拆分。这和爬楼梯问题有点像,都是从子问题推导到当前问题。