139. Word Break

题目

给定一个字符串 s 和一个字典 wordDict。返回 true 如果 s 能被分成不同的一个或多个序列。

解析

要判断一个字符串是否可以被单词分割，即可以先搜索一个完整的单词，然后判断剩余单词是否可以分割。
特别的，如果单词长度为 0 则不需要再进行 dict 判断。
f(x) = word[:k1] & f(k1:x) | word[:k2] & f(k2:x)

伪代码

for i in s
  if isdict(s[:i]) && wordBreak(s[i:], wordDict)
      return true

isdict(s, wordDict)

for i in wordDict
    if s == wordDict[i]
      return true

代码

func wordBreak(s string, wordDict []string) bool {
    if len(s) == 0 {
        return true
    }
    bs := []byte(s)
    for i := range bs {
        if isDict(string(bs[:i+1]), wordDict) && wordBreak(string(bs[i+1:]), wordDict) {
            return true
        }
    }
    return false
}

func isDict(s string, wordDict []string) bool {
    for i := range wordDict {
        if s == wordDict[i] {
            return true
        }
    }
    return false
}

优化

这个算法因为在迭代遍历过程中会反复匹配同样的字段，截取浪费大量的时间。基于此，我们添加一个记忆单元，在该记忆单元中，该记忆单元存储这个字符串中字符起止地址是否是字典中的数据。

if s in mm
  return isdict(s)
for i in s
  if isDict(s[:i]) && wordBreak(s[i:], wordDict)
      mm[s] = true
      return true
mm[s] = false

代码

func wordBreak(s string, wordDict []string) bool {
    mm := make(map[string]bool)
    
    for i := range wordDict {
        mm[wordDict[i]] = true
    }
    mm[""] = true
    return wordBreakRec(s, mm)
}

func wordBreakRec(s string, mm map[string]bool) bool {
    if is, ok := mm[s]; ok {
        return is
    }
    bs := []byte(s)
    for i := range bs {
        if is,ok := mm[string(bs[:i+1])]; ok && is && wordBreakRec(string(bs[i+1:]), mm) {
            mm[s] = true
            return true
        }
    }
    mm[s] = false
    return false
}

image.png