139. Word Break
139. Word Break
🟠 🔖 字典树
记忆化搜索
数组
哈希表
字符串
动态规划
🔗 LeetCode
题目
Given a string s
and a dictionary of strings wordDict
, return true
if s
can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s
andwordDict[i]
consist of only lowercase English letters.- All the strings of
wordDict
are unique.
题目大意
给你一个字符串 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
解题思路
思路一:递归+记忆化搜索
递归 + 记忆化搜索:使用递归函数
helper
来判断从当前位置i
开始的子串能否被拆分。通过遍历字典中的单词,检查当前位置开始的子串是否以这些单词开头。如果是,则递归调用helper
判断剩余部分,如果能被拆分,则返回true
。记忆化搜索:为了避免重复计算,使用一个数组
dp
来记录每个位置的计算结果。dp[i]
的值为 1 表示从位置i
开始的子串可以被拆分,为 0 表示不能被拆分,初始化为 -1。返回结果:调用
helper(0)
,即从字符串的起始位置开始判断整个字符串是否能被拆分。
时间复杂度: 最坏情况下的时间复杂度为
O((n/m)^m)
,其中n
表示字符串的长度,m
表示字典中单词的平均长度,最坏情况下每个位置i
可能需要遍历所有m
长度的单词,递归的深度可能达到n/m
层。具体复杂度取决于能否利用记忆化搜索避免重复计算。空间复杂度: 记忆化搜索中使用了一个数组
dp
,其长度为字符串的长度,因此空间复杂度为 O(n)。递归调用的栈深度也会占用一些额外的空间。
思路二:动态规划-DP table
动态规划:可以使用动态规划来解决这个问题。定义一个一维数组
dp
,其中dp[i]
表示字符串的前i
个字符是否可以被拆分。状态转移方程:对于每个位置
i
,可以考虑将字符串拆分成两部分,即s[0:i]
和s[i:n]
(n
是字符串的长度)。如果前半部分可以被拆分,并且后半部分在字典中,那么整个字符串就可以被拆分。因此,状态转移方程为:dp[i] = dp[j] && s[j:i] ∈ wordDict
其中,0 ≤ j < i
。初始化:初始化
dp[0]
为true
,表示空字符串可以被拆分。遍历计算:从字符串的第一个字符开始,依次计算
dp[i]
直到最后一个字符。结果:返回
dp[n]
,其中n
是字符串的长度,表示整个字符串是否可以被拆分。
- 时间复杂度:
O(n^2)
- 两层循环,遍历字符串的所有可能子串。 - 空间复杂度:
O(n)
- 使用了一个数组来存储中间状态。
代码
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
const n = s.length;
const dp = new Array(n).fill(-1);
const helper = (i) => {
if (i == n) return true;
if (dp[i] !== -1) return dp[i] == 1;
for (let word of wordDict) {
let len = word.length;
if (i + len > n) {
continue;
}
if (word !== s.substring(i, i + len)) {
continue;
}
if (helper(i + len)) {
dp[i] = 1;
return true;
}
}
dp[i] = 0;
return false;
};
return helper(0);
};
/**
* @param {string} s
* @param {string[]} wordDict
* @return {boolean}
*/
var wordBreak = function (s, wordDict) {
const n = s.length;
if (n === 0) {
return false;
}
// 初始化动态规划数组
const dp = new Array(n + 1).fill(false);
dp[0] = true; // 空字符串可以被拆分
// 遍历计算动态规划数组
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordDict.includes(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
// 返回结果
return dp[n];
};
相关题目
- [140. 单词拆分 II](https://leetcode.com/problems/word-break-ii)
- [2707. 字符串中的额外字符](https://leetcode.com/problems/extra-characters-in-a-string)