题目描述
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.
题目分析
首先考虑如何判断字符串a为字符串s的一个子序列？朴素的想法就是利用2个指针ap, sp，各自从2个字符串的起始位置向后扫描；每找到一个相同字符，ap,sp各自向后移动一位；否则只移动sp；如果s遍历完，a也遍历完，则认为a是s的一个子序列；
由于题目中说明字符串数组长度最大有5000个，字符串分别也有最大50000和50个字符；如果按照以上方式比较，显然效率较低；特别是如果s中前面一部分字符如果和a不相符，仍然要进行比较，这部分浪费较大，有优化空间，因此从这方面入手，我们考虑如下解法：
首先，我们遍历字符串s，建立一个map；这个map记录的是每个字符出现的下标的集合；
有了这个集合后，我们就可以快速的找到当前要查找的字符串a中的某个字符是否存在，以及它的下标；当我们查找之后的字符时，只要保证新的字符存在这样一个下标，使得这个下标大于上一个字符的下标，就表示可以匹配成功；
按照以上思路，解法如下:
示例代码
// 利用map记录s中各个字符的下标，然后遍历words中每一个word，查找比当前下标位置更大的字符下标
// 如果都能找到，说明word是s的一个subsequence，否则不是
func numMatchingSubseq(s string, words []string) int {
ans := 0
m := make(map[byte][]int)
// 建立字符下标集合map
for i := 0; i < len(s); i++ {
m[byte(s[i])] = append(m[byte(s[i])], i)
}
for _, v := range words {
// 初始下标为-1
curpos := -1
find := true
for i := 0; i < len(v); i++ {
// 如果字符不存在，直接break
if _, ok := m[v[i]]; !ok {
find = false
break
}
// 如果当前字符的最大下标都不大于上一个字符的下标，表示无法匹配，break
if m[v[i]][len(m[v[i]])-1] <= curpos {
find = false
break
}
// 遍历当前字符的下标，找到第一个大于上个字符位置的下标
for _, iv := range m[v[i]] {
if iv > curpos {
curpos = iv
break
}
}
}
if find {
ans++
}
}
return ans
}
优化代码
初始解法提交AC后， 发现效率一般；继续逛评论区，发现一个更巧妙的思路，称作 Next Letter Pointers
这个算法的思路如下:
- 按照首字母将words中的字符串group进一个map或者二维数组
- 遍历字符串s，对于每一个字符，去1中的map或者数组中找对应的字符串；
- 如果字符串存在，那么将这些字符串首字母去除；如果剩余长度为0，说明已经匹配；如果不为0，则继续按照新的首字母重新group进map或者数组
- 重复上述循环判断过程即可
参照这个思路，实现代码如下:
// Next letter pointers
// 按照首字母将words组织进map或者slice里，然后依次遍历s中的字符；
// 每遍历一个字符，就将有相同首字母的words进行如下处理:
// 1. 去除首字母
// 2. 如果剩余长度为0，说明为subsequence
// 3. 如果剩余长度不为0，重新组织进map或者slice中; 继续上述循环
func numMatchingSubseqV2(s string, words []string) int {
// 使用二维数组记录同首字母的字符串
m := make([][]string, 26)
for _, v := range words {
prefix := v[0] - 'a'
m[prefix] = append(m[prefix], v)
}
ans := 0
for i := 0; i < len(s); i++ {
prefix := s[i] - 'a'
targets := m[prefix]
if len(targets) == 0 {
continue
}
m[prefix] = []string{}
for _, v := range targets {
// 如果字符串长度为1，说明已经匹配
if len(v) == 1 {
ans++
continue
}
// 否则使用第二个字母作为key，append到二维数组中
pf := v[1] - 'a'
// 注意这里，append的是去除了首字母的新字符串
m[pf] = append(m[pf], v[1:])
}
}
return ans
}