算法 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) {

vector> pos(26);

for(int i=0;i

pos[s[i]-'a'].push_back(i); //把s中出现的字母 将其位置按从小到大记录

int res=words.size();

for(int i=0;i

{

if(words[i].size()>s.size())

{

res--;

continue;

}

int p=-1;

for(int j=0;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

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);

}

}

相关链接