跳至主要內容

139. 单词拆分


139. 单词拆分open in new window

🟠   🔖  字典树 记忆化搜索 数组 哈希表 字符串 动态规划  🔗 力扣open in new window LeetCodeopen in new window

题目

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 and wordDict[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

解题思路

思路一:递归+记忆化搜索

  1. 递归 + 记忆化搜索:使用递归函数 helper 来判断从当前位置 i 开始的子串能否被拆分。通过遍历字典中的单词,检查当前位置开始的子串是否以这些单词开头。如果是,则递归调用 helper 判断剩余部分,如果能被拆分,则返回 true

  2. 记忆化搜索:为了避免重复计算,使用一个数组 dp 来记录每个位置的计算结果。dp[i] 的值为 1 表示从位置 i 开始的子串可以被拆分,为 0 表示不能被拆分,初始化为 -1。

  3. 返回结果:调用 helper(0),即从字符串的起始位置开始判断整个字符串是否能被拆分。

复杂度分析

  • 时间复杂度: 最坏情况下的时间复杂度为 O((n/m)^m),其中 n 表示字符串的长度,m 表示字典中单词的平均长度,最坏情况下每个位置 i 可能需要遍历所有 m 长度的单词,递归的深度可能达到 n/m 层。具体复杂度取决于能否利用记忆化搜索避免重复计算。

  • 空间复杂度: O(n),记忆化搜索中使用了一个数组 dp,其长度为字符串的长度。递归调用的栈深度也会占用一些额外的空间。


思路二:动态规划-DP table

  1. 动态规划:可以使用动态规划来解决这个问题。定义一个一维数组 dp,其中 dp[i] 表示字符串的前 i 个字符是否可以被拆分。

  2. 状态转移方程:对于每个位置 i,可以考虑将字符串拆分成两部分,即 s[0:i]s[i:n]n 是字符串的长度)。如果前半部分可以被拆分,并且后半部分在字典中,那么整个字符串就可以被拆分。因此,状态转移方程为:dp[i] = dp[j] && s[j:i] ∈ wordDict 其中,0 ≤ j < i

  3. 初始化:初始化 dp[0]true,表示空字符串可以被拆分。

  4. 遍历计算:从字符串的第一个字符开始,依次计算 dp[i] 直到最后一个字符。

  5. 结果:返回 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);
};

相关题目

题号标题题解标签难度
140单词拆分 IIopen in new window字典树 记忆化搜索 数组 4+
2707字符串中的额外字符open in new window字典树 数组 哈希表 2+