匹配子序列的单词数

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

例如， “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

提示:

1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-matching-subsequences
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1

要求解子序列的单词数，子问题是判断一个字符串是不是一个字符串的子序列。可以采用双指针的算法，指针i指向字符串s的起点，指针j指向字符串t的起点，如果s[i]==s[j],则i++，j++;如果s[i] != s[j],则i ++；最后判断指针j是不是指向字符串t的终点。正确性判断：如果存在子序列的话，必然是可以直接从第一个匹配的字符开始的，比如字符串后面有子序列ab，那么上一个a也可以组成子序列ab。不过本题朴素的匹配做法时间复杂度并不符合要求。

code

class Solution {
public:
    bool is_sub(string & s, string & t)
    {
        int i = 0,j = 0;
        int n = s.size(),m = t.size();

        while(i < n && j < m)
        {
            if(s[i] == t[j]) j ++;
            i ++;
        }

        return j == m;
    }

    int numMatchingSubseq(string s, vector<string>& words) {
        
        int ans = 0;

        for(int i = 0;i < words.size();i ++)
        {
            if(is_sub(s,words[i])) ans ++;
        }

        return ans;
    }
};

优化思路

朴素的匹配做法时间复杂度主要体现在指针i是一步一步的往前移动并匹配的，我们可以记录下字符串s的每一个字符的位置列表，这样匹配t[j]的时候就可以直接在s的字符列表中查找，记录下s的当前位置cur，保证查找的位置大于cur即可，由于字符的位置是递增的，可以使用二分查找算法。注意：二分查找有两个板子，查找左侧区间的端点mid = (l + r + 1)/2,查找右侧区间的端点，mid = （l+ r）/2.

code

class Solution {
public:

   
    bool is_sub(string & s, string &t, vector<vector<int>> & pos)
    {
        int cur = -1,j = 0;

        while(j < t.size())
        {
            int l = 0,r = pos[t[j] - 'a'].size() -1;
            if(r == -1) return false;
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(pos[t[j] - 'a'][mid] > cur) r = mid;
                else l = mid + 1;
            }
            //cout<<pos[t[j] - 'a'][l]<<" ";
           
            if(pos[t[j] - 'a'][l] > cur) 
            {
                cur = pos[t[j] - 'a'][l];
                j ++;
            }
            else return false;
            //j ++;
        }
        //cout<<endl;
        return true;
    }

    int numMatchingSubseq(string s, vector<string>& words) {
        
        int ans = 0;
        
        vector<vector<int>> pos(26);
        for(int i = 0;i < s.size();i ++)
            pos[s[i] - 'a'].push_back(i);

        for(int i = 0;i < words.size();i ++)
            if(is_sub(s,words[i],pos)) ans ++;
        
        return ans;
    }
};