题目描述：
哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
注意：本题相对原题稍作改动，只需返回未识别的字符数
今日学习：
1.复习reduce
2.动规动规又是动规我哭了
3.字典树的概念
4.对象动态属性赋值obj[name]
题解：
1.错误原因：有时候不一定全用较长的单词剩下的字符少，有可能短单词会更紧凑剩的更少
2.错误原因：理解错题意了
3.动规
4.错误原因：同1
5.字典树
/**
* @param {string[]} dictionary
* @param {string} sentence
* @return {number}
*/
//思路一：
//1.在句子中遍历字典里的单词，查找单词在句子中出现的次数，记录到times中
var respace = function(dictionary, sentence) {
let slen = sentence.length
let dlen = dictionary.length
if(slen == 0) return 0
dictionary.sort((a, b) => b.length - a.length)
//字典中每个单词出现的次数
let times = new Array(dlen).fill(0)
//字典中每个单词的长度
let lens = new Array(dlen)
for(let i = 0; i < dlen; i++) {
lens[i] = dictionary[i].length
}
for(let i = 1; i <= slen; i++){
//每次比较时候用到的temp次数，按理说每一次i，temp里只能出现一个1
let temp = new Array(dlen).fill(0)
for(let j = 0; j < dlen; j++){
let word = lens[j]
if(dictionary[j] == sentence.substring(i - word, i) && word <= i){
temp[j]++
}
}
let index
if(temp.reduce((total,item) => total + item) > 1) {
index = temp.indexOf(1)
for(let k = index + 1; k < dlen; k++) {
if(temp[k] == 1) {
index = lens[k] > lens[index] ? k : index
}
}
times[index]++
}else {
index = temp.indexOf(1)
if(index != -1) {
times[index]++
}
}
}
for(let i = 0; i < dlen; i++) {
slen -= lens[i] * times[i]
}
return slen
};
//思路二：
//1.遍历s，查找是否有字典内的字符串，不在开始位置就数量+2，在起始位置就+1
//【理解错题意了，jesstim一共七个字符，所以输出7，而不是7个单词】
//2.截取后面的s，继续查找
/*var respace = function(dictionary, sentence) {
for(let i = 0; i < sentence.length; i++) {
for(let j = i + 1; j < sentence.length; j++) {
let s = sentence.slice(i, j)
}
}
}*/
//思路三：
//动规
var respace = function (dictionary, sentence) {
let len = sentence.length
if(len == 0) return 0
let dp = new Array(len + 1).fill(0)
for(let i = 1; i <= len; i++){
// 先假设加进来的字符没有组成新词，那么dp[i]相比于dp[i-1]直接多1
dp[i] = dp[i - 1] + 1
// 接着讨论如果新加进来的字符和之前组成了一个词的情况
// 与字典中的每一个字符串比较看是否组成了新词
for(let j = 0; j < dictionary.length; j++){
let word = dictionary[j].length
// 如果组成了新词，更新dp，按最小的未识别算
// 因为像her，brother这种，明显使用brother使得未识别字符数最少
if(dictionary[j] == sentence.substring(i - word, i) && word <= i){
dp[i] = Math.min(dp[i], dp[i - word])
}
}
}
return dp[len]
}
//思路四：正则匹配+替换
const respace = (dictionary, sentence) => {
dictionary.sort((a, b) => b.length - a.length); // 由大到小进行排序
let count = 0
for (let i = 0; i < dictionary.length; i++) {
sentence = sentence.replace(new RegExp(dictionary[i], 'g'), ' ');
}
for(let i = 0; i < sentence.length; i++) {
if(sentence[i] == ' ')
count++
}
return sentence.length - count;
// return sentence
};
//思路五：字典树
/**
* @param {string[]} dictionary
* @param {string} sentence
* @return {number}
*/
var respace = function (dictionary, sentence) {
var len = sentence.length;
if (!len) return 0;
// 生成字典树
const trie = {};
for (let i = 0, l = dictionary.length; i < l; i++) {
const word = dictionary[i];
let node = trie;
for (let j = 0, m = word.length; j < m; j++) {
const char = word[j];
node = node[char] || (node[char] = {});
}
// 标记单词结束
node['$'] = true;
}
const cache = new Array(len).fill(Infinity);
let res = Infinity;
// DFS
const stack = [0];
const countStack = [0];
while (stack.length) {
// 当前单词匹配起点
const index = stack.pop();
// 当前未识别字符数
const count = countStack.pop();
// 从开头到前一个字符的子串，未识别字符数的最小值
const n = cache[index];
// console.log(`已匹配子串 ${sentence.slice(0, index)}, 未识别字符数为 ${count}`);
// 未识别字符数不小于当前最小值，放弃该分支
if (count >= n || count >= res) continue;
// 已完成整个字符串的匹配
if (index >= len) {
// console.log(`■■■■■ 匹配完成，未识别字符数为 ${count} ■■■■■`);
if (count < res) res = count;
continue;
}
// 进行单词匹配
let i = index;
let node = trie[sentence[i++]];
// 如果匹配到一个字符的单词，选择该单词的分支为更优解，放弃未识别的分支
if (!(node && node['$'])) {
// 添加当前字符为未识别字符的分支
stack.push(index + 1);
countStack.push(count + 1);
}
// 寻找可识别的单词
while (node) {
// 成功识别到单词，添加分支
if (node['$']) {
// console.log(`识别到单词 ${sentence.slice(index, i)}`);
stack.push(i);
countStack.push(count);
}
node = node[sentence[i++]];
}
if (count < n) cache[index] = count;
}
return res;
};