> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/word-break/107word-break.md).

# 139.Word Break (M)

## 1.Description(Medium)

Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words.

**Example**

Given s =`"lintcode"`, dict =`["lint", "code"]`.

Return true because**"lintcode"**can be break as`"lint code"`.

## 2.Code

**Solution 1:DFS**

看到这题第一反应是DFS枚举查找，直到“探”到string尾部则算成功。但题目并不要求给出是如何break的，而只要判断是否能break。对这类判断“是”与“否”的可以用DFS暴力解决的题.

对于这道题，我们首先考虑暴力的方法。本题相当于用多个字符串组成该字符串，那么我们就枚举所有可能的放入字符串的方法，通过深度优先搜索，尝试所有可能。 对于一个字符串，考虑字典中的每个前缀是否是这个字典中的单词。若不是，则跳过该单词。若是则将该前缀从字符串中删除后，判断剩下的字符串能否由字典里的单词组成。 由于题目的数据加强，此题已经无法使用常规的DFS方式通过，我们更推荐更优秀的DP来实现。

#### 代码思路

使用深度优先搜索，记录字符串，字典，以及当前需要判断的字符串的起始点 从当前字符串的起始点开始判断

#### 代码框架

```
定义dfs
    递归的出口
    如果起始点已经在字符串的尾部
        停止，返回可以组成该字符串
    如果还未到结尾，枚举下一个字符串的长度。
        对于每种可能，判断该字符串是否在字典中
        如果在字典中：
            取出该字符串，判断剩下的是否可以
    找完所有可能后，仍然不行，直接返回这段字符串无法找到答案
    
    
```

时间复杂度：O(2^n)，考虑当s = "aaaaaaaaaaab", dict = {"a", "aa", "aaa", ...., "aaaaaaaaa"} 空间复杂度：O(N)，递归深度最深为N层

#### 相关问题：

LintCode 582. Word Break II LintCode 683. Word break III LintCode 123. Word Search

```
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        return dfs(s, dict, 0); 
    }
    
    /**
     * 递归的定义
     * 判断字符串s[start: ]能否通过wordDict中的单词组成
    **/
    public boolean dfs(String s, Set<String> dict, int now) {
        // 递归的出口
        if (now == s.length()) {
            return true;
        }
        
        // 递归的拆解，枚举下一个字符串的长度len
        for (int len = 1; now + len <= s.length(); len++) {
            // 判断s[now: now + len]是否满足条件
            if (dict.contains(s.substring(now, now + len)) && dfs(s, dict, now + len)) {
                return true;
            }
        }
        return false;
    }
}
```

**Solution 2: Dynamic Programming**

state: f\[i] 表示前i个字符能不能被完美切分。

function：f\[i] = OR{f\[j]}+ j+1\~i is a word (优化：j只需要到最长的单词长度即可)

例: j=0,1,3,5 f\[i] =f\[0] || f\[1] || f\[3] || f\[5]

Initialize: f\[0]=true

answer:f\[n]

```
 public boolean wordBreak(String s, Set<String> dict) {

         if (s == null || s.length() == 0) {
             return true;
         }

        int n=s.length();

        int maxlen=0;
        for(String str:dict){
            int len=str.length();
            if(len>maxlen){
                maxlen=len;
            }
        }

        //state;
        boolean[] cut=new boolean[n+1];

        //Initialize:
        cut[0]=true;

        //function:
        for(int i=1;i<=n;i++){
            cut[i]=false;
            for(int lastwordlength=1;
                    lastwordlength<=maxlen && lastwordlength<=i;
                    lastwordlength++){

            String word=s.substring(i-lastwordlength, i);
                if(cut[i-lastwordlength] && dict.contains(word)){
                    cut[i]=true;
                    break;
            }
        }
    }
        return cut[n];


    }
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/word-break/107word-break.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.