题目

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。

像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。

在处理标点符号和大小写之前，你得先把它断成词语。

当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。

假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

示例：输入： dictionary = ["looked","just","like","her","brother"]

sentence = "jesslookedjustliketimherbrother"

输出： 7

解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。

提示：0 <= len(sentence) <= 1000

dictionary中总字符数不超过 150000。

你可以认为dictionary和sentence中只包含小写字母。

解题思路分析

1、动态规划+字典树；时间复杂度O(n^2)，空间复杂度O(n)

func respace(dictionary []string, sentence string) int {
   n := len(sentence)
   root := &Trie{
      next: [26]*Trie{},
   }
   for i := 0; i < len(dictionary); i++ {
      root.Insert(reverse(dictionary[i])) // 反序插入
   }
   dp := make([]int, n+1)
   for i := 1; i <= n; i++ {
      dp[i] = dp[i-1] + 1 // 上一个长度+1
      cur := root
      for j := i; j >= 1; j-- {
         value := int(sentence[j-1] - 'a')
         if cur.next[value] == nil {
            break
         } else if cur.next[value].ending > 0 { // 找到，更新
            dp[i] = min(dp[i], dp[j-1])
         }
         if dp[i] == 0 {
            break
         }
         cur = cur.next[value]
      }
   }
   return dp[n]
}

func reverse(s string) string {
   arr := []byte(s)
   for i := 0; i < len(s)/2; i++ {
      arr[i], arr[len(s)-1-i] = arr[len(s)-1-i], arr[i]
   }
   return string(arr)
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

type Trie struct {
   next   [26]*Trie // 下一级指针，如不限于小写字母，[26]=>[256]
   ending int       // 次数（可以改为bool）
}

// 插入word
func (this *Trie) Insert(word string) {
   temp := this
   for _, v := range word {
      value := v - 'a'
      if temp.next[value] == nil {
         temp.next[value] = &Trie{
            next:   [26]*Trie{},
            ending: 0,
         }
      }
      temp = temp.next[value]
   }
   temp.ending++
}

2、动态规划+哈希；时间复杂度O(n^2)，空间复杂度O(n)

func respace(dictionary []string, sentence string) int {
   n := len(sentence)
   m := make(map[string]bool)
   for i := 0; i < len(dictionary); i++ {
      m[dictionary[i]] = true
   }
   dp := make([]int, n+1)
   for i := 1; i <= n; i++ {
      dp[i] = dp[i-1] + 1 // 上一个长度+1
      for j := i; j >= 1; j-- {
         str := sentence[j-1 : i]
         if m[str] == true {
            dp[i] = min(dp[i], dp[j-1])
         }
         if dp[i] == 0 {
            break
         }
      }
   }
   return dp[n]
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

总结

Medium题目，使用动态规划，借助字典树或者哈希；类似的题目还有leetcode 139.单词拆分