讨论/算法和数据结构/792. 匹配子序列的单词数/
792. 匹配子序列的单词数

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:
输入: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3

解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。

注意:

所有在words和 S 里的单词都只由小写字母组成。
S 的长度在 [1, 50000]。
words 的长度在 [1, 5000]。
words[i]的长度在[1, 50]

展开讨论
demongodYY发起于 2020-05-09

要的就是暴力

var numMatchingSubseq = function(S, words) {
    let count = 0;
    
    for (const word of words) {
        let index = -1;
        let _count = 0;
        for (const str of word) {            
            _count++;
            const _index = S.indexOf(str, index+1);

            if (_index === -1) {
                break;
            } else {
                index = _index;
            }

            if (_count === word.length) {
                count++;
            }
        }
    }
    return count;
};

再来个不太暴力的

var numMatchingSubseq = function(S, words) {
    const bucket = Array.from({ length: 26 }, () => []);
    
    let count = 0;

    for (const word of words) {
        bucket[word.charCodeAt(0) - 97].push(word); // a的unicode是97
    }
    
    for (const str of S) {
        const list = bucket[str.charCodeAt(0) - 97];
        bucket[str.charCodeAt(0) - 97] = [];

        for (let word of list) {
            if (word.length > 1) {
                word = word.slice(1);
                if (word) {
                    bucket[word.charCodeAt(0) - 97].push(word);
                }
            } else {
                count++;
            }
        }
    }
    return count;
};
展开全部 3 讨论