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
}