Description
Given a string s and an array of words, return the number of words that are a subsequence of s. A subsequence maintains relative order but not necessarily contiguous.
Examples
Input:
s = "abcde", words = ["a","bb","acd","ace"]Output:
3Explanation:
a, acd, ace are subsequences.
Input:
s = "programming", words = ["pro","gram","ming","program","grommit","prom"]Output:
5Explanation:
pro (p-r-o), gram (g-r-a-m), ming (m-i-n-g), program (p-r-o-g-r-a-m), and prom (p-r-o-m) are all subsequences of 'programming'. grommit is not a subsequence because there is no second 'm' after 'gro' in the string.
Input:
s = "xyz", words = ["x","y","z","xy","xz","yz","xyz","zyx",""]Output:
8Explanation:
All words except 'zyx' are subsequences. Single characters x, y, z appear in order. Pairs xy, xz, yz maintain relative order. xyz matches exactly. Empty string is always a subsequence. zyx fails because z comes after y and x in the string, violating subsequence order.
Constraints
- •
1 ≤ s.length ≤ 5 × 10⁴