面试题-17.13-恢复空格.md

题目描述

恢复空格

题目简述

你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

分类

中等 动态规划

思路

思路1

/**
 * @param {string[]} dictionary
 * @param {string} sentence
 * @return {number}
 */
const 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]
};

• 问题分析
  • 这道题思路挺难想的，直接参考思路。
  • dp[i]用于储存0 - i的未识别字符数
  • 每次循环使用当前字符串，结合字典中的字符串，进行判断末尾是否存在识别字符，否则为dp[i - 1] + 1。如果有，则最少字符数等于除开末尾识别自负的字符串的dp值，和dp[i - 1] + 1进行比较，取更小值。
  • 最终推导出的dp[lastIndex]就是结果。