题目描述

给定字符串S，找出字符串列表words中是S的子序列的字符串的个数。字符串只包含英文小写字母。

样例

输入：S = "abcde", words = ["a", "bb", "acd", "ace"]
输出：3
说明："a", "acd", "ace"是S的子串

算法1

(二分查找) $O(mlog(n))$

words[i]是S的子序列，则words[i]中每个字母一定出现在S中，且在S中保留相对先后顺序，例如”acd”是”abcde”的子序列，说明在S中要满足”a”在”c”前面，”c”在”d”前面，因此判断words[i]是否是S的子序列，只需要判断words[i]中每个字母在S中的下标是否满足相对先后顺序即可。

因此可以考虑维护一个下标数组pos，记录在S中每个字母出现的下标位置，然后再去看words[i]中的每个字母，是否能在S中满足相对先后顺序即可。例如判断”adb”是否是”abcbcede”的子序列，首先”a”在S中的下标为[0]，”d”在S中的下标为[6]，”b”在S中的下标为[1, 3]，发现在”adb”中b在d后面，因此在b的下标数组中查找是否存在下标大于6，但是在S中b的下标都小于,6，因此可以判断”adb”不是”abcbcede”的子序列。

时间复杂度分析：$O(mlog(n))$, m是words列表的长度，n是字符串S的长度。

C++ 代码

class Solution {
public:
    int search(vector<int>&pos, int k){//二分查找下标数组中第一个大于k的数，k是words[i]中上一个字母的下标
        if(pos.size()==0)
            return -1;
        int l = 0;
        int r = pos.size()-1;
        if(k>=pos[r])
            return -1;
        while(l<r){
            int mid = (l+r)/2;
            if(pos[mid]>k)
                r = mid;
            if(pos[mid]<=k)
                l = mid+1;
        }
        if(pos[l]>k)
            return l;
        else
            return -1;
    }
    int numMatchingSubseq(string S, vector<string>& words) {
        vector<vector<int>>pos;
        int res = 0;
        for(int i= 0;i<26;i++){//只有26个英文小写字母
            vector<int>v;
            pos.push_back(v);
        }
        for(int i = 0;i<S.size();i++){
            pos[S[i]-'a'].push_back(i);
        }
        for(int i =0;i<words.size();i++){
            bool flag = true;
            int k = -1;//k表示上一个字母的下标，下一个字母的下标必须大于k
            for(int j = 0;j<words[i].size();j++){
                k = search(pos[words[i][j]-'a'], k);//二分查找
                if(k<0){//说明下标数组中找不到比k大的下标了，该字符串不是S的子序列
                    flag = false;
                    break;
                }
                k = pos[words[i][j]-'a'][k];//更新k
            }
            if(flag)//说明该字符串是S的子序列
                res += 1;
        }
        return res;
    }
};