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 * 1041 <= words.length <= 50001 <= words[i].length <= 50s and words[i] consist of only lowercase English letters.
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
d = defaultdict(deque)
for w in words:
d[w[0]].append(w)
ans = 0
for c in s:
for _ in range(len(d[c])):
t = d[c].popleft()
if len(t) == 1:
ans += 1
else:
d[t[1]].append(t[1:])
return ans(code-box)
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Deque<String>[] d = new Deque[26];
Arrays.setAll(d, k -> new ArrayDeque<>());
for (String w : words) {
d[w.charAt(0) - 'a'].add(w);
}
int ans = 0;
for (char c : s.toCharArray()) {
var q = d[c - 'a'];
for (int k = q.size(); k > 0; --k) {
String t = q.pollFirst();
if (t.length() == 1) {
++ans;
} else {
d[t.charAt(1) - 'a'].offer(t.substring(1));
}
}
}
return ans;
}
}(code-box)
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<queue<string>> d(26);
for (auto& w : words) d[w[0] - 'a'].emplace(w);
int ans = 0;
for (char& c : s) {
auto& q = d[c - 'a'];
for (int k = q.size(); k; --k) {
auto t = q.front();
q.pop();
if (t.size() == 1)
++ans;
else
d[t[1] - 'a'].emplace(t.substr(1));
}
}
return ans;
}
};(code-box)
func numMatchingSubseq(s string, words []string) (ans int) {
d := [26][]string{}
for _, w := range words {
d[w[0]-'a'] = append(d[w[0]-'a'], w)
}
for _, c := range s {
q := d[c-'a']
d[c-'a'] = nil
for _, t := range q {
if len(t) == 1 {
ans++
} else {
d[t[1]-'a'] = append(d[t[1]-'a'], t[1:])
}
}
}
return
}(code-box)
Solution 2
PythonJavaC++Go
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
Solution 3
PythonJavaC++Go
class Solution:
def numMatchingSubseq(self, s: str, words: List[str]) -> int:
def check(w):
i = -1
for c in w:
j = bisect_right(d[c], i)
if j == len(d[c]):
return False
i = d[c][j]
return True
d = defaultdict(list)
for i, c in enumerate(s):
d[c].append(i)
return sum(check(w) for w in words)(code-box)
class Solution {
private List<Integer>[] d = new List[26];
public int numMatchingSubseq(String s, String[] words) {
Arrays.setAll(d, k -> new ArrayList<>());
for (int i = 0; i < s.length(); ++i) {
d[s.charAt(i) - 'a'].add(i);
}
int ans = 0;
for (String w : words) {
if (check(w)) {
++ans;
}
}
return ans;
}
private boolean check(String w) {
int i = -1;
for (int k = 0; k < w.length(); ++k) {
int c = w.charAt(k) - 'a';
int j = search(d[c], i);
if (j == d[c].size()) {
return false;
}
i = d[c].get(j);
}
return true;
}
private int search(List<Integer> t, int x) {
int left = 0, right = t.size();
while (left < right) {
int mid = (left + right) >> 1;
if (t.get(mid) > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}(code-box)
class Solution {
public:
int numMatchingSubseq(string s, vector<string>& words) {
vector<vector<int>> d(26);
for (int i = 0; i < s.size(); ++i) d[s[i] - 'a'].emplace_back(i);
int ans = 0;
auto check = [&](string& w) {
int i = -1;
for (char& c : w) {
auto& t = d[c - 'a'];
int j = upper_bound(t.begin(), t.end(), i) - t.begin();
if (j == t.size()) return false;
i = t[j];
}
return true;
};
for (auto& w : words) ans += check(w);
return ans;
}
};(code-box)
func numMatchingSubseq(s string, words []string) (ans int) {
d := [26][]int{}
for i, c := range s {
d[c-'a'] = append(d[c-'a'], i)
}
check := func(w string) bool {
i := -1
for _, c := range w {
t := d[c-'a']
j := sort.SearchInts(t, i+1)
if j == len(t) {
return false
}
i = t[j]
}
return true
}
for _, w := range words {
if check(w) {
ans++
}
}
return
}(code-box)
