0139.word-break.md

0139.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

题意

给定一个非空字符串ss和一个非空词典wordDictwordDict,判断ss是否能被分割成一个或多个单词分隔的序列。 注意，词典中的词可以用多次，词典中没有重复的单词。

题解

思路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)]
}

递归

思路2

```go package main

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

}

```

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm