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

  • 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