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 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
给一个字符串，看是否可以由字典中的单词拆分成以空格隔开的单词序列。
用动态规划DP来解，某一个字符前面的字符串的拆分方法可能有多种，后面的拆分要看前面的拆分组合。
State: dp[i], 表示到字符i时，前面1~i的字符串能否拆分
Function: dp[i] = (dp[i - j] + str[j:i] in dict) for j in range(i), 到字符i能否拆分取决于每一个以i结尾的str[j-i]字符 是否在字典里并且j字符之前的字符串可以拆分
Initialize: dp[0] = true
Return: dp[n], 到最后一个字符n是否能拆分
在截取j 到 i 字符串，判断是否在字典中时，可以先判断字典中的字符串最大长度，超出长度就不用再循环了。
此方法可以告诉我们是否能拆分字典中的单词，但不能给出具体拆分内容。如果要知道具体拆分内容要用DFS，见140题。
Java:
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for(int i=1; i <= s.length(); i++){
for(int j=0; j < i; j++){
if(f[j] && dict.contains(s.substring(j, i))){
f[i] = true;
break;
}
}
}
return f[s.length()];
}
}
Java:
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
boolean[] f = new boolean[s.length() + 1];
f[0] = true;
for(int i = 1; i <= s.length(); i++){
for(String str: dict){
if(str.length() <= i){
if(f[i - str.length()]){
if(s.substring(i-str.length(), i).equals(str)){
f[i] = true;
break;
}
}
}
}
}
return f[s.length()];
}
}
Java:
public boolean wordBreak(String s, Set<String> dict) {
if(s==null || s.length()==0)
return true;
boolean[] res = new boolean[s.length()+1];
res[0] = true;
for(int i=0;i<s.length();i++)
{
StringBuilder str = new StringBuilder(s.substring(0,i+1));
for(int j=0;j<=i;j++)
{
if(res[j] && dict.contains(str.toString()))
{
res[i+1] = true;
break;
}
str.deleteCharAt(0);
}
}
return res[s.length()];
}
Python:
class Solution(object):
def wordBreak(self, s, wordDict):
n = len(s)
max_len = 0
for string in wordDict:
max_len = max(max_len, len(string))
can_break = [False for _ in xrange(n + 1)]
can_break[0] = True
for i in xrange(1, n + 1):
for j in xrange(1, min(i, max_len) + 1):
if can_break[i-j] and s[i-j:i] in wordDict:
can_break[i] = True
break
return can_break[-1]
Python: wo
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in xrange(1, n + 1):
for j in xrange(0, i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
break
return dp[-1]
C++:
class Solution {
public:
bool wordBreak(string s, unordered_set<string>& wordDict) {
const int n = s.length();
size_t max_len = 0;
for (const auto& str: wordDict) {
max_len = max(max_len, str.length());
}
vector<bool> canBreak(n + 1, false);
canBreak[0] = true;
for (int i = 1; i <= n; ++i) {
for (int l = 1; l <= max_len && i - l >= 0; ++l) {
if (canBreak[i - l] && wordDict.count(s.substr(i - l, l))) {
canBreak[i] = true;
break;
}
}
}
return canBreak[n];
}
};
Followup: 返回其中的一个解，如果要返回全部解需要用140. Word Break II的方法，一个解要简单很多。F jia
Java:
class Solution {
public String wordBreak(String s, Set<String> dict) {
if (s == null || s.isEmpty() || dict == null) {
return "";
}
boolean[] dp = new boolean[s.length() + 1];
String[] words = new String[s.length() + 1];
dp[0] = true;
words[0] = "";
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
if (words[j].isEmpty()) {
words[i] = s.substring(j, i);
} else {
words[i] = words[j] + " " + s.substring(j, i);
}
}
}
}
if (dp[s.length()]) {
return words[s.length()];
} else {
return "";
}
}
public static void main(String[] args) {
String s = new String("catsanddog");
String[] d = {"cat", "cats", "and", "sand", "dog"};
Set<String> dict = new HashSet<String>();
dict.addAll(Arrays.asList(d));
System.out.println(s);
System.out.println(dict);
Solution sol = new Solution();
System.out.println(sol.wordBreak(s, dict));
}
}
类似题目：
[LeetCode] 140. Word Break II 单词拆分II
[LeetCode] 97. Interleaving String 交织相错的字符串