792. Number of Matching Subsequences
Medium
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 * 10^41 <= words.length <= 50001 <= words[i].length <= 50sandwords[i]consist of only lowercase English letters.
func numMatchingSubseq(s string, words []string) int {
m := make(map[int][]int)
for i:=0; i<26; i++ {
m[i] = make([]int, 0)
}
for i:=0; i<len(s); i++ {
m[int(s[i] - 'a')] = append(m[int(s[i] - 'a')], i)
}
ans := 0
table := make(map[string]bool) // 紀錄已經出現過的 word
for _, word := range words {
if isexisted, ok := table[word]; ok {
if isexisted {
ans++
}
continue
}
if len(word) > len(s) {
continue
}
if isMatch(m, word) {
ans++
table[word] = true
} else {
table[word] = false
}
}
return ans
}
func isMatch(m map[int][]int, word string) bool {
pre := -1
for i:=0; i<len(word); i++ {
arr := m[int(word[i] - 'a')]
if len(arr) == 0 {
return false
}
if arr[len(arr) - 1] <= pre {
return false
}
for _, index := range arr {
if index > pre {
pre = index
break
}
}
}
return true
}