Welcome to Subscribe On Youtube

792. Number of Matching Subsequences

Description

Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

 

Example 1:

Input: s = "abcde", words = ["a","bb","acd","ace"]
Output: 3
Explanation: There are three strings in words that are a subsequence of s: "a", "acd", "ace".

Example 2:

Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2

 

Constraints:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• s and words[i] consist of only lowercase English letters.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int numMatchingSubseq(String s, String[] words) {
          Deque<int[]>[] d = new Deque[26];
          Arrays.setAll(d, k -> new ArrayDeque<>());
          for (int i = 0; i < words.length; ++i) {
              d[words[i].charAt(0) - 'a'].offer(new int[] {i, 0});
          }
          int ans = 0;
          for (char c : s.toCharArray()) {
              var q = d[c - 'a'];
              for (int t = q.size(); t > 0; --t) {
                  var p = q.pollFirst();
                  int i = p[0], j = p[1] + 1;
                  if (j == words[i].length()) {
                      ++ans;
                  } else {
                      d[words[i].charAt(j) - 'a'].offer(new int[] {i, j});
                  }
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int numMatchingSubseq(string s, vector<string>& words) {
          vector<queue<pair<int, int>>> d(26);
          for (int i = 0; i < words.size(); ++i) d[words[i][0] - 'a'].emplace(i, 0);
          int ans = 0;
          for (char& c : s) {
              auto& q = d[c - 'a'];
              for (int t = q.size(); t; --t) {
                  auto [i, j] = q.front();
                  q.pop();
                  if (++j == words[i].size())
                      ++ans;
                  else
                      d[words[i][j] - 'a'].emplace(i, j);
              }
          }
          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
  
  

• 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