恢复空格-面试题 17.13

[sl1673495]

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"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 中只包含小写字母。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/re-space-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

动态规划，从前向后遍历，dp[i] 表示从 0 ~ i 的字符串由 dictionary 中的单词拼接而成所需要的最少的未识别字符个数。也就是题目求什么，就把状态定义成什么。

状态转移方程，遍历 dictionary 中的每一个单词，用这个单词的长度 len 去取 sentence[0 ~ i] 从后往前数 len 位的字符串，

1. 如果两者匹配上了，说明这个单词可以去抵消掉字符串中的后部分，那么 dp[i] 就可以更新为 dp[i - len]，也就是减掉这个单词整体的长度以后的最少的未识别字符个数。
2. 如果未找到匹配的，那么 dp[i] = dp[i - 1] + 1，也就是上一位的最少未识别个数加上当前这个未识别的字符的长度。

最后只需要返回 dp[sentence.length] 即可表明在 sentence 的长度完全考虑进去时，最少未识别字符个数。

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {number}
 */
let respace = function (dictionary, sentence) {
  let n = sentence.length
  let dp = [0]
  for (let i = 1; i <= n; i++) {
    let min = dp[i - 1] + 1
    for (let word of dictionary) {
      if (sentence.substring(i - word.length, i) === word) {
        min = Math.min(min, dp[i - word.length])
      }
    }
    dp[i] = min
  }
  return dp[n]
}