Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/792.html

792. Number of Matching Subsequences

Level

Medium

Description

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example:

Input:

S = “abcde”

words = [“a”, “bb”, “acd”, “ace”]

Output: 3

Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50].

Solution

One solution is to check whether each word in words is a subsequence of S, and count the number of subsequences, which is quite time-consuming since S is looped over many times.

A better solution is to maintain buckets for each letter. For each word in words, for each letter, store the following letters in the buckets. If the end of word is reached, add the counter by 1.

• Java
• C++
• Python
• Go

• class Solution {
      public int numMatchingSubseq(String S, String[] words) {
          int count = 0;
          ArrayList<Node>[] heads = new ArrayList[26];
          for (int i = 0; i < 26; i++)
              heads[i] = new ArrayList<Node>();
          for (String word : words)
              heads[word.charAt(0) - 'a'].add(new Node(word, 0));
          char[] array = S.toCharArray();
          for (char c : array) {
              ArrayList<Node> oldBucket = heads[c - 'a'];
              heads[c - 'a'] = new ArrayList<Node>();
              for (Node node : oldBucket) {
                  node.index++;
                  int wordLength = node.word.length();
                  if (node.index == wordLength)
                      count++;
                  else
                      heads[node.word.charAt(node.index) - 'a'].add(node);
              }
              oldBucket.clear();
          }
          return count;
      }
  }
  
  class Node {
      String word;
      int index;
  
      public Node(String word, int index) {
          this.word = word;
          this.index = index;
      }
  }
  

• // OJ: https://leetcode.com/problems/number-of-matching-subsequences/
  // Time: O(S + NWlogS)
  // Space: O(S)
  class Solution {
  public:
      int numMatchingSubseq(string s, vector<string>& A) {
          vector<int> index[26];
          for (int i = 0; i < s.size(); ++i) index[s[i] - 'a'].push_back(i);
          int ans = 0;
          for (auto &w : A) {
              int i = 0, j = 0;
              for (; i < w.size(); ++i) {
                  auto &v = index[w[i] - 'a'];
                  auto it = lower_bound(begin(v), end(v), j);
                  if (it == end(v)) break;
                  j = *it + 1;
              }
              ans += i == w.size();
          }
          return ans;
      }
  };
  

• class Solution:
      def numMatchingSubseq(self, s: str, words: List[str]) -> int:
          d = defaultdict(deque)
          for i, w in enumerate(words):
              d[w[0]].append((i, 0))
          ans = 0
          for c in s:
              for _ in range(len(d[c])):
                  i, j = d[c].popleft()
                  j += 1
                  if j == len(words[i]):
                      ans += 1
                  else:
                      d[words[i][j]].append((i, j))
          return ans
  
  ############
  
  class Solution(object):
      def numMatchingSubseq(self, S, words):
          """
          :type S: str
          :type words: List[str]
          :rtype: int
          """
          m = dict()
          def isMatch(word, d):
              if word in m:
                  return m[word]
              prev = -1
              for w in word:
                  i = bisect.bisect_left(d[w], prev + 1)
                  if i == len(d[w]):
                      return 0
                  prev = d[w][i]
              m[word] = 1
              return 1
          
          d = collections.defaultdict(list)
          for i, s in enumerate(S):
              d[s].append(i)
          ans = [isMatch(word, d) for word in words]
          return sum(ans)
  

• func numMatchingSubseq(s string, words []string) (ans int) {
  	type pair struct{ i, j int }
  	d := [26][]pair{}
  	for i, w := range words {
  		d[w[0]-'a'] = append(d[w[0]-'a'], pair{i, 0})
  	}
  	for _, c := range s {
  		q := d[c-'a']
  		d[c-'a'] = nil
  		for _, p := range q {
  			i, j := p.i, p.j+1
  			if j == len(words[i]) {
  				ans++
  			} else {
  				d[words[i][j]-'a'] = append(d[words[i][j]-'a'], pair{i, j})
  			}
  		}
  	}
  	return
  }
  

All Problems

All Solutions