# 139. Word Break

## Description

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

Tags: Math, String

## 题解

### 思路1

``````package main

func wordBreak(s string, wordDict []string) bool {
dp := make([]bool, len(s)+1)
dp[0] = true

for i := 0; i < len(dp); i++ {
if dp[i] {
for _, word := range wordDict {
//    巧妙的运用 i + word len 避免2层循环
if i+len(word) <= len(s) && s[i:i+len(word)] == word {
dp[i+len(word)] = true
}
}
}
}
return dp[len(s)]
}
``````

### 递归

func wordBreak3(s string, wordDict []string) bool { ans := make(map[string]bool) return helper(s, wordDict, ans) }

// s 每次比对的字符串 // wordDict 目标字典列表 // 匹配结果 func helper(s string, wordDict []string, ans map[string]bool) bool { // 终止条件 if len(s) == 0 { return true }

``````if res, ok := ans[s]; ok {
return res
}

for _, word := range wordDict {
if len(word) > len(s) || word != s[:len(word)] {
continue
}

if helper(s[len(word):], wordDict, ans) {
ans[s] = true
return true
}

}
ans[s] = false

return false
``````

}

```