哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"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个未识别字符。
/**
* @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]
}
哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前,你得先把它断成词语。当然了,你有一本厚厚的词典 dictionary,不过,有些词没在词典里。假设文章用 sentence 表示,设计一个算法,把文章断开,要求未识别的字符最少,返回未识别的字符数。
注意:本题相对原题稍作改动,只需返回未识别的字符数
提示:
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
位的字符串,dp[i]
就可以更新为dp[i - len]
,也就是减掉这个单词整体的长度以后的最少的未识别字符个数。dp[i] = dp[i - 1] + 1
,也就是上一位的最少未识别个数加上当前这个未识别的字符的长度。最后只需要返回
dp[sentence.length]
即可表明在sentence
的长度完全考虑进去时,最少未识别字符个数。