Leetcode # 792. Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/

Brute-force (Time Limit Exceeded)

Time Complexity: O(len(s) * len(words))

在檢查 s 的每一個字元時
都要遍歷 words 一次
浪費太多不必要的時間

class Solution:
  def numMatchingSubseq(self, s: str, words: List[str]) -> int:
    ans = 0
    for i in range(len(s)):
      for j in range(len(words)):
        if len(words[j]) > 0 and words[j][0] == s[i]:
          words[j] = words[j][1:]
          if words[j] == "":
            ans += 1
      # print(words)
    return ans

Next Letter Pointers

修正上一個 solution
在檢查 s[i] 時
只檢查 words 中那些「下一個需檢查的字元是 s[i] 者」

\begin{align}
&\text{Time Complexity: }O(len(s) + \sum_i{len(words[i])}) \\
&\text{Space Complexity: }O(len(words))
\end{align}

class Solution:
  def numMatchingSubseq(self, s: str, words: List[str]) -> int:
    ans = 0
    left_words = collections.defaultdict(list)
    for word in words:
      left_words[word[0]].append(word)
    
    for c in s:
      if c not in left_words:
        continue
      
      new_left_word_c = []
      for word in left_words[c]:
        if len(word) == 1:
          ans += 1
        elif word[1] == c:
          new_left_word_c.append(word[1:])
        else:
          left_words[word[1]].append(word[1:])
      
      if len(new_left_word_c) > 0:
        left_words[c] = new_left_word_c
      else:
        left_words.pop(c)
        
    return ans

Last Updated on 2023/08/16 by A1go