792. Number of Matching Subsequences #

Problem #

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 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
s and words[i] consist of only lowercase English letters.

Problem Summary #

Given a string S and a word dictionary words, find the number of words in words[i] that are subsequences of S.

Solution Approach #

If each string in the words array is matched against the source string S every time, this brute-force solution will time out. The reason for the timeout is that the string S is traversed multiple times. Is there a more efficient method?
Divide the strings in the words array into 26 buckets according to their first letter. Traverse the source string S once from the beginning. For each letter scanned, it hits one of the 26 buckets, and the strings in that bucket are modified. For example: currently traversing to ‘o’, and the data in the buckets is ‘a’ : [‘amy’,‘aop’], ‘o’: [‘oqp’,‘onwn’]; after adjusting the data in the ‘o’ bucket, the state of each bucket becomes ‘a’ : [‘amy’,‘aop’], ‘q’: [‘qp’], ‘n’: [‘nwn’]. After scanning the entire string S from beginning to end, if a string in a certain bucket is emptied, it means that the string satisfies being a subsequence of S. Accumulate the number of strings that satisfy being subsequences to get the final answer.

Code #

package leetcode

func numMatchingSubseq(s string, words []string) int {
	hash, res := make([][]string, 26), 0
	for _, w := range words {
		hash[int(w[0]-'a')] = append(hash[int(w[0]-'a')], w)
	}
	for _, c := range s {
		words := hash[int(byte(c)-'a')]
		hash[int(byte(c)-'a')] = []string{}
		for _, w := range words {
			if len(w) == 1 {
				res += 1
				continue
			}
			hash[int(w[1]-'a')] = append(hash[int(w[1]-'a')], w[1:])
		}
	}
	return res
}