> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/graph-search/139.word-break.md).

# 139.Word-Break

## 139. Word Break

## 题目地址

<https://leetcode.com/problems/word-break/>

## 题目描述

```
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
```

## 代码

### Approach 1: Brute Force

**Complexity Analysis**

* Time complexity : O(n^n). Consider the worst case where s = "aaaaaaa" and every prefix of s is present in the dictionary of words, then the recursion tree can grow upto n^n.
* Space complexity : O\_(\_n). The depth of the recursion tree can go upto n\_n\*.

```java
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, new HashSet(wordDict), 0);
  }

  public boolean dfs(String s, Set<String> wordDict, int start) {
    if (start == s.length()) {
      return true;
    }
    for (int end = start + 1; end <= s.length(); end++) {
      if (wordDict.contains(s.substring(start, end)) && 
          dfs(s, wordDict, end)) {
        return true;
      }
    }

    return false;
  }
}
```

### Approach #2 Recursion with memoization

**Complexity Analysis**

* Time complexity : O(n^2). Size of recursion tree can go up to n^2.
* Space complexity : O(n). The depth of recursion tree can go up to n.

```java
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
  }

  public boolean dfs(String s, Set<String> wordDict, int start, Boolean[] memo) {
    if (start == s.length()) {
      return true;
    }

    if (memo[start] != null) {
      return memo[start];
    }

    for (int end = start + 1; end <= s.length(); end++) {
      if (wordDict.contains(s.substring(start, end)) 
          && dfs(s, wordDict, end, memo)) {
        return memo[start] = true;
      }
    }

    return memo[start] = false;
  }
}
```

### Approach #3 Using Breadth-First Search

**Complexity Analysis**

* Time complexity : O(n^2). For every starting index, the search can continue till the end of the given string.
* Space complexity : O\_(\_n). Queue of atmost n size is needed.

```java
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    Queue<Integer> queue = new LinkedList<>();
    int[] visited = new int[s.length()];

    queue.add(0);
    while (!queue.isEmpty()) {
      int start = queue.remove();
      if (visited[start] == 0) { // 这一步判断很关键，不然会超时
        for (int end = start + 1; end <= s.length(); end++) {
          if (wordDictSet.contains(s.substring(start, end))) {
            queue.add(end);
            if (end == s.length()) {
              return true;
            }
          }
        }

        visited[start] = 1;
      }
    }

    return false;
  }
}
```

### Approach #4 Using Dynamic Programming

**Complexity Analysis**

* Time complexity : O(n^2). Two loops are their to fill dp array.
* Space complexity : O\_(\_n). Length of p array is n + 1.

```java
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    boolean[] dp = new boolean[s.length() + 1];

    dp[0] = true;
    for (int end = 1; end <= s.length(); end++) {
      for (int start = 0; start < end; start++) {
        if (dp[start] && wordDictSet.contains(s.substring(start, end))) {
          dp[end] = true;
          break;
        }
      }
    }

    return dp[s.length()];
  }
}
```