JZX轻语：简

LeetCode 792 - 匹配子序列的单词数

发表于2024年05月03日

#哈希表 #多指针 #数组

朴素想法是，每遍历s的一个字符时，分别更新words中每个单词的匹配指针(一开始从0开始，可视作为下一个期望的指针)位置：如果匹配上，则往右移动指针。上述朴素做法会超时，因为需要遍历每一个单词，而往往不匹配的情况非常多。因此，使用一个哈希表来缓存每个单词下一次期望字符的信息，其中键为下一次期望字符，而值为单词列表，其中这些单词的下一次期望字符为对应键。当遍历s中的字符时，从哈希表中取出下一次期望字符为该字符的单词列表，然后更新它们的指针，指向新的下一次期望字符，并更新哈希表即可。这样可以省掉遍历所有单词和比较时间。

from collections import defaultdict


class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        points_map = defaultdict(list)
        for i, word in enumerate(words):
            points_map[word[0]].append((i, 0))
        ans = 0
        for ch in s:
            matched_points = points_map[ch]
            points_map[ch] = []
            for word_index, word_cur_pos in matched_points:
                word = words[word_index]
                word_cur_pos += 1
                if word_cur_pos == len(word):
                    ans += 1
                else:
                    points_map[word[word_cur_pos]].append((word_index, word_cur_pos))

        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/number-of-matching-subsequences/