面试题 17.13. 恢复空格

面试题 17.13. 恢复空格

题目描述

给定一个字典 dictionary 和 一串字符串sentence， 在这串字符串中尽可能多的从字典中找到相应的值，返回未识别的字符

输入：
dictionary = [“looked”,”just”,”like”,”her”,”brother”]
sentence = “jesslookedjustliketimherbrother”
输出： 7
解释： 断句后为”jess looked just like tim her brother”，共7个未识别字符。

解题思路

• 一开始想的是 根据我们现实生活中这样查字典这样，比如 looked, 先翻到L如果字典有l 开头的那再找 o 如果没有那直接退出，这时候就要构建字典树

• 我们直接遍历字符串sentence, 然后 跟字典里的那些 词对比一下，然后最小的那个就可以了

我们以 sentence = 'jelookedss', dictionary = ["looked"] 为例子

dp:

i	0	1	2	3	4	5	6	7	8	9	10
sentence	j	e	l	o	o	k	e	d	s	s
dp[]	0	1	2	3	4	5	6	7	2	3	4

请注意我们dp[0] = 0 所以dp[1] 对应的应该是 sentence[0], 就是后移了一位
看上面的图，当我们i = 7 的时候 我们找到了looked，这是我们字典里的，所以我们dp[7+1] 的值应该是dp[2] => dp[7 - 6 + 1] 即 sentence[1] 的时候，因为前面的都是在字典中找不到的,
替代公式： 要是找到的情况下 dp[i + 1] = Math.min(dp[i + 1], dp[i - 字典词长度 + 1])

动态规划

var respace = function(dictionary, sentence) {
    let dp = [0];
    let length = sentence.length;

    if(dictionary.length == 0) {
        return length;
    }

    for(let i = 0; i < length; i++) {
        dp[i + 1] = dp[i] + 1;

        for(let j = 0; j < dictionary.length; j++ ) {
            const l = dictionary[j].length
            if(dictionary[j] == sentence.substring(i - l + 1 , i + 1 )) {
                dp[i + 1] = Math.min(dp[i + 1], dp[i - l + 1] );
            }
        }
    }

    return dp[length];
};

字典树

var respace = function(dictionary, sentence) {
    let cache = []
    for (let j = 0;j < sentence.length + 1;j ++) {
        cache.push(new Map)
    }
    let dp = new Array(sentence.length+1).fill(0);
    let trie = {};
    let n = sentence.length;
    if (sentence === "") return 0;

    // 构建字典树
    for(let word of dictionary) {
        let node = trie;
        for(let c of word) {
            if (node[c] == undefined) {
                node[c] = {}
            }
            node = node[c];
        }
        node["#"] = "#";
    }
    // 预处理出字典中存在的所有下标区间 cache[j].get[k] == true 表示[k,j]区间的单词在字典中能找到。
    // 我们寻找字典开头，要是选找到开头的话继续往下找字典，要是遇到 # 那么就结束了，对于每个字符都是都一样，最后记录当前位置字符到字典结束的长度
    for(let i = 1; i <= n; i++) {
        let node = trie;
        for(let j = i; j <= n; j++) {
            let c = sentence[j-1];
            if (!node[c]) {
                break;
            }
            node = node[c];
            if (node['#'] != undefined) {
                cache[j].set(i, true);
            }
        }
    }
    for (let j = 1;j <= n;j ++) {
        dp[j] = dp[j-1] + 1;
        for(let [k,v] of cache[j]){
            dp[j] = Math.min(dp[j], dp[k-1])
        }
    } 
    return dp[n];
};