发表于 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 题目链接