Cool说丨力扣392

简介: 392. 判断子序列

392. 判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

示例 1:s = "abc", t = "ahbgdc"

返回 true.

示例 2:s = "axc", t = "ahbgdc"

返回 false.

后续挑战 :

如果有大量输入的 S,称作S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

第一版自己写的,比较耗费空间

执行用时 :52 ms, 在所有 cpp 提交中击败了83.51%的用户

内存消耗 :17.1 MB, 在所有 cpp 提交中击败了21.38%的用户

boolisSubsequence(strings, stringt) {

   intlen=t.size(),count=0;

   for (unsignedi=0,j=0; i<s.size(); ++i) {

       while (true) {

           if (j<len&&s[i] ==t[j]) {

               count++;

               j++;

               break;

           }

           elseif (j<len)

               j++;

           else

               break;

       }

       if (j==len&&i<s.size()-1) {

           returnfalse;

       }

   }

   if (count==s.size())

       returntrue;

   else

       returnfalse;

}

后续挑战,很不错

后续挑战,输入量大,小写字母创建25的二维数组,存储t的坐标,这样就可以把s的判断直接转为坐标的判断,dp[0]代表了存储了a出现在t的所有的位置,逐个字符判断s的字符顺序是否在t内,直接返回结果。时间复杂度O(t.size()+2000):分别为创建数组需要O(t.size()),索引是递增的使用二分查找s的单个字符20次之内就可找到需要O(100*20)。适用大量的输入判断子序列。

boolisSubsequence(strings, stringt) {        

   vector<vector<int>>dp(26);

   inttag=-1;

   for(inti=0;i<t.size();i++)

       dp[t[i]-'a'].push_back(i);

   for(inti=0;i<s.size();i++){

       intnow=s[i]-'a';

       intleft=0,right=dp[now].size()-1;

       while(left<right){

           intmid=(left+right)/2;

           if(dp[now][mid]>tag)

               right=mid;

           else

               left=mid+1;

       }

       if(right<left||dp[now][left]<tag)returnfalse;

       tag=dp[now][left];

   

}

returntrue;

}


目录
相关文章
|
人工智能 C# C++
Cool说丨力扣153、454
153. 寻找旋转排序数组中的最小值 454. 四数相加 II
130 1
|
C# C++
Cool说丨力扣287/792/378
关注博主,获取更多知识
103 0
|
C# C++ 索引
Cool说丨力扣162
162. 寻找峰值
95 0
|
存储 C# C++
Cool说丨力扣29/34
关注博主。获取更多知识
103 0
|
C# C++
Cool说丨力扣744、704
744. 寻找比目标字母大的最小字母 704. 二分查找
106 0
|
C#
Cool说丨力扣475
475. 供暖器
113 0
|
机器学习/深度学习 算法 C#
Cool说丨力扣202
202. 快乐数
100 0
|
C#
Cool说丨力扣167
167. 两数之和 II - 输入有序数组
70 0
|
C# C++
Cool说丨力扣374、441
441. 排列硬币 374. 猜数字大小
89 0
|
C# C++
Cool说丨力扣367
367. 有效的完全平方数
209 0