160 - 139 单词拆分

题目

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。 注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

解答

https://leetcode-cn.com/problems/word-break/solution/jing-dian-dpzhan-sheng-100python-by-qia-fu-qia-fu/

首先取出字典中最大字符串的长度。定义结果是全0数组。

0，说明该点之前不能构成字典中的key；1说明可以构成。

用外循环i来遍历字符串；内循环p从i向前，到最大字符串之间，遍历。

• 如果res[p]==1，说明之前的字符串，在字典中有

  而且，s[p:i+1]在字典中，说明i就是一个可以拆分的节点。

• 或者p是字符串的第一个，且s[p:i+1]在字典中，那就是第一个字符串。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        maxlen = 0
        for word in wordDict:
            if len(word) > maxlen:
                maxlen = len(word)
        res = [0]*len(s)
        for i in range(len(s)):
            p = i
            while p >= 0 and i-p <= maxlen:
                if (res[p] == 1 and s[p+1:i+1] in wordDict) or (p == 0 and
                                                                s[p:i+1] in wordDict):
                    res[i] = 1
                    break
                p -= 1
        return res[-1]

Runtime: 32 ms, faster than 96.24% of Python3 online submissions for Word Break.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Word Break.

func wordBreak(s string, wordDict []string) bool {
    var maxlen int
    data := make(map[string]bool, len(wordDict))
    for _, v := range wordDict {
        if len(v) > maxlen {
            maxlen = len(v)
        }
        data[v] = true
    }
    res := make([]bool, len(s))
    for i := 0; i < len(s); i++ {
        p := i
        for p >= 0 && i-p <= maxlen {
            _, ok1 := data[s[p+1:i+1]]
            _, ok2 := data[s[p:i+1]]
            if (res[p] && ok1) || (p == 0 && ok2) {
                res[i] = true
                break
            }
            p--
        }
    }
    return res[len(res)-1]
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Word Break.

Memory Usage: 2.1 MB, less than 100.00% of Go online submissions for Word Break.

var wordBreak = function(s, wordDict) {
  let maxlen = 0
  wordDict.forEach(e => {
    if (e.length > maxlen) {
      maxlen = e.length
    }
  })
  const res = new Array(s.length)
  for (let i = 0; i < s.length; i++) {
    let p = i
    while (p >= 0 && i - p <= maxlen) {
      if ((res[p] && wordDict.indexOf(s.slice(p + 1, i + 1)) > -1) || (p ===
          0 && wordDict.indexOf(s.slice(p, i + 1)) > -1)) {
        res[i] = true
        break
      }
      p--
    }
  }
  if (res[res.length - 1] === undefined) {
    return false
  }
  return res[res.length - 1]
};

Runtime: 52 ms, faster than 96.82% of JavaScript online submissions for Word Break.

Memory Usage: 33.8 MB, less than 100.00% of JavaScript online submissions for Word Break.