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 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 层。具体复杂度取决于能否利用记忆化搜索避免重复计算。

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

思路二：动态规划-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);
};

动态规划-DP table

/**
 * @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
• 2707. 字符串中的额外字符

- [140. 单词拆分 II](https://leetcode.com/problems/word-break-ii)
- [2707. 字符串中的额外字符](https://leetcode.com/problems/extra-characters-in-a-string)