# Problem 139: Word Break

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

## 思路

* 这道题的思路类似于 Palindrome Partitioning II。不过有不同的一点是，他加入了 maxLength 这个 trick，只比到最大的长度就可以了。
* word break 要始终保证前面的元素存在一种方法是可以 break 的，这就要求每次都要判断前面的 true 或 false 值。

![](/files/-Lpv9xq3PuNHe0mKB50G)

```java
public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int maxLength = getMaxLength(wordDict);
        // 动态规划的数组的 size 通常要加 1,因为之前有个 base
        boolean[] canSegment = new boolean[s.length() + 1];
        canSegment[0] = true;
        for (int i = 1; i <= s.length(); i++) { // dp 的循环一定是 <=，
                                                // 因为他的 size 比原来多一个
            // 首先设成 false
            canSegment[i] = false;
            for (int lastWord = 1; lastWord <= maxLength && lastWord <= i; lastWord++) {
                // 如果前半部分没法 break，那么就跳过，找下一个
                if (!canSegment[i - lastWord]) {
                    continue;
                }
                String word = s.substring(i - lastWord, i);
                if (wordDict.contains(word)) {
                    canSegment[i] = true;
                    break;
                }
            }
        }

        return canSegment[s.length()];
    }

    private int getMaxLength(Set<String> wordDict) {
        int maxLength = 0;
        for (String word : wordDict) {
            maxLength = Math.max(word.length(), maxLength);
        }
        return maxLength;
    }

}
```

## 易错点

1. 数组长度

   数组长度为`s.length() + 1`，也就是说从单词的开头到单词的屁股后面都要cut一下
2. 简化trick

   ```java
   int lastWord = 1; lastWord <= maxLength && lastWord <= i; lastWord++
   ```

   中间的这两个条件，相辅相成。lastWord不需要比最大的length大，因为再大了字典里就没有这个词了。
3. 跳过条件

   ```java
   if (!canSegment[i - lastWord]) {
     continue;
   }
   ```

   ![](/files/-Lpv9xq6Zc0MLHkn_GZE)

   这里的`lastWord`是标记位置。后面的`s.substring(i - lastWord, i)`,  &#x20;
4. 我当时做的时候写的判断条件是： &#x20;

   ```java
   String word = s.substring(lastword + 1, i);
   ```

   这样写会报错，数据溢出； &#x20;

   正确的写法应该是： &#x20;

   ```java
   String word = s.substring(i - lastword, i);
   ```

   原因就是 lastword 有可能会溢出的，比如一个字母作为单词的情况，lastword + 1 就溢出了。

   另外，substring 方法：**后面的 string 不大写！**


---

# 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://liuyang89116.gitbook.io/my-leetcode-book/chapter_5_dynamic_programming/sequence-lei-xing/problem_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.