139 Word Break 单词拆分
Description:
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example:
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
题目描述:
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 :
示例 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
思路:
动态规划
dp[i]表示 s[:i]可以被字典分割
转移方程 dp[i + 1] = check(s[:j] and dp[j]), j = 1, 2, ..., i
初始状态 dp[0] = true, 表示空字符串可以被分割
检查字符串需要使用 set存储, 可以将查找时间降低到 O(1)
可以用字典树和剪枝(只要j - i > wordDict中字符串的最长值, 就终止搜索)加快速度
时间复杂度O(n ^ 2), 空间复杂度O(n)
代码:
C++:
class Solution
{
public:
bool wordBreak(string s, vector<string>& wordDict)
{
unordered_set<string> d(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 0; i < s.size(); i++) for (int j = i + 1; j <= s.size(); j++) if (dp[i] and d.find(s.substr(i, j - i)) != d.end()) dp[j] = true;
return dp.back();
}
};
Java:
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean dp[] = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 0; i < s.length(); i++) for (int j = i + 1; j <= s.length(); j++) if (dp[i] && set.contains(s.substring(i, j))) dp[j] = true;
return dp[s.length()];
}
}
Python:
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
d, dp = set(wordDict), [True] + [False] * len(s)
for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
if dp[i] and s[i:j] in d:
dp[j] = True
return dp[-1]
