leetcode.792 匹配子序列的单词数 哈希表 + 二分优化

792. 匹配子序列的单词数

目录

1、c++版 

2、java

暴力思路：

最暴力的思路是双指针 也就是指针i指向s 指针j指向word  

如果s[i]==word[j] 则将 i 和 j 同时向后移一个

否则移动 i指针 

如果i指针指向s末尾时 如果j也同时指向word末尾 则说明是子序列 否则不是

但该方法时间复杂度会tle 因此要在此基础上进行优化

二分哈希表优化：

暴力做法里 我们要在不匹配时不断把i指针一个一个向后移 

我们可以把s中每个字母的下标按从小到大顺序存在哈希表pos里

比如：【aabccb】  word: "bac"

则 pos[a]={0,1}

    pos[b]={2,5}

    pos[c]={3,4}

这样对于需要进行匹配的word[j]  可以通过在pos里进行二分查找 找到第一个大于当前i指针的位置，如果该位置不存在，则说明不匹配，否则之间将i指针移动到当前位置

比如：

        初始化 i 指针为-1

        word:"bac"

        查找b -> 找到了 -> i指针移向2

        查找a -> 二分后找不到比2大的位置 -> 该位置不存在 -> 不匹配

        word:"abcb"

        查找a -> 找到了 -> i指针移向0

        查找b -> 找到了 -> i指针移向2

        查找c -> 找到了 -> i指针移向3

        查找b -> 找到了 -> i指针移向5 -> 匹配

1、c++版 

class Solution {
public:
    int numMatchingSubseq(string s, vector& words) {
        vectorint>> pos(26);
        for(int i=0;isize();i++)
            pos[s[i]-'a'].push_back(i); //把s中出现的字母 将其位置按从小到大记录
 
        int res=words.size();
        for(int i=0;isize();i++)
        {
            if(words[i].size()>s.size())
            {
                res--;
                continue;
            }
            int p=-1;
            for(int j=0;jsize();j++)
            {
                auto &ps=pos[words[i][j]-'a']; //获取该字符的pos序列
                auto it=upper_bound(ps.begin(),ps.end(),p); //查找比p大的第一个下标位置
                if(it==ps.end()) //如果没查找到 则说明不是子序列
                {
                    res--;
                    break;
                }
                p=*it; //找到了 p指针向后移
            }
        }
        return res;
    }
};

2、java

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        List[] pos=new ArrayList[26];
        for(int i=0;i<26;i++) pos[i]=new ArrayList<>();
 
        for(int i=0;i'a'].add(i);
        
        int res=words.length;
        for(String w:words)
        {
            if(w.length()>s.length())
            {
                res--;
                continue;
            }
            int p=-1;
            for(int i=0;i
            {
                char ch=w.charAt(i);
                if(pos[ch-'a'].isEmpty()||pos[ch-'a'].get(pos[ch-'a'].size()-1)<=p) //如果二分位置直接卡出去了
                {
                    res--;
                    break;
                }
                p=find(pos[ch-'a'],p);
            }
        }
        return res;
    }
 
    public int find(List a,int target)
    {
        int l=0,r=a.size()-1;
        while(l
        {
            int mid=l+r>>1;
            if(a.get(mid)>target) r=mid;
            else l=mid+1;
        }
        return a.get(l);
    }
 
}