# 139.Word Break

**139.Word Break**

> 给定一个非空字符串 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
```

方法：

1. 最直观的想法是暴力判断，从第一个字符开始，找到剩下的所有字符在字典中的情况。如果没找到，则返回false。代码如下：

```
class Solution {
private:
    unordered_map<string,int> dict;
    bool dictbreak(string s)
    {
        if(dict[s]) return true;
        for(int i=1;i<s.length();i++)
        {
            string tmp=s.substr(0,i);
            if(dict[tmp] && dictbreak(s.substr(i,s.length()-i)))
                return true;
        }
        return false;
    }
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        for(int i=0;i<wordDict.size();i++)
            dict[wordDict[i]]++;
    
        return dictbreak(s);
    }
    
};
```

结果超时啦～算算时间复杂度吧，主要影响时间的是`dictbreak`函数中的循环里的递归调用，设字符串长度为n，计算次数（只考虑循环）为T(n),则T(n)=1+T(n-1)+1+T(n-2)+...+1+T(1)+1+T(0);\
其中，T(0)=0,T(1)=1， 则T(n)=sigma(T(n-1))+n;\
所以，sigma(T(n)) = sigma(T(n-1))+T(n)=n+2sigma(T(n-1));\
因此有，sigma(T(n)) +n =2sigma(T(n-1))+2(n-1)+2;\
递归一下，有sigma(T(n))+n = 2^(n-1) x sigma(T(1)+1)+sigma(2^(n-1)=O(2^n); 由于T(n)和sigma(T(n-1))+n复杂度相同，所以时间复杂度为指数级别。。。\
当然不会通过。

1. 从右侧开始判断，将左侧判断过的放入内存中，之后不必再次判断。一样采用递归的方法。 代码如下：

```
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.cbegin(),wordDict.cend());
        
        return wordBreak(s,dict);
    }
    bool wordBreak(string s, const unordered_set<string>& wordDict) {
        if(mem.count(s)) return mem[s];
        if(wordDict.count(s)) return mem[s]=true;
        for(int i=0;i<s.length();i++)
        {
            const string left=s.substr(0,i);
            const string right=s.substr(i);
            if(wordDict.count(right) && wordBreak(left,wordDict))
                return mem[s]=true;
        }
        return mem[s]=false;
    }
private:
    unordered_map<string,bool> mem;
};
```

此时时间复杂度为O(n^2) 最后给出leetcode排名比较靠前的一种解法:

```
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        if(s.empty()){
            return true;
        }
        for(auto s:wordDict){
            wordset.insert(s);
            if(s.size()>maxl){
                maxl=s.size();
            }
        }
        vector<bool>flag(s.size()+1,false);
        flag[0]=true;
        for(int i=0;i<s.size();i++){
          for(int j=0;j<min(maxl,i+1);j++){
                if(flag[i-j]&&(wordset.find(s.substr(i-j,j+1))!=wordset.end())){
                    flag[i+1]=true;
                    break;
                }
        }
        }
        return flag[s.size()];
    }
private:
    unordered_set<string> wordset;
    int maxl=0;
};
    
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dfine.gitbook.io/leetcode/139.word_break.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.