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^4
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 50
  • s and words[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
}
​