讨论/算法和数据结构/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]

展开讨论
共 3 个讨论

要的就是暴力

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;
};
func numMatchingSubseq(S string, words []string) int {
    count := 0
    for i := 0; i < len(words); i++ {
        stat := 0
        word := words[i]
        if len(word) > len(S) {
            continue
        }else {
            for i := 0; i < len(S); i++ {
                if word[stat] == S[i]{
                    stat++
                    if stat == len(word) {
                        count++
                        break
                    }
                }
            } 
        }
    }
    return count
}

挨个字母匹配暴力破解

var numMatchingSubseq = function (S, words) {
    const isSubWord = function (s, word) {
        let pos = -1;
        for (let i = 0; i < word.length; i++) {
            pos = s.indexOf(word[i], pos + 1);
            if (pos == -1) return 0;
        }
        return 1;
    };

    return words.reduce((count, word) => count + isSubWord(S, word), 0)
};