正规网站建设排行,怎么提交网站关键词,设计建设网站公司哪家好,常州做网站哪家快1. 题目
给定字符串 s 和 t #xff0c;判断 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长#xff08;长度 ~ 500,000#xff09;#xff0c;而 s 是个短字符串#xff08;长度 100#xff09;。
字符串的一个子序列是原始…1. 题目
给定字符串 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 的子序列。在这种情况下你会怎样改变代码
来源力扣LeetCode 链接https://leetcode-cn.com/problems/is-subsequence 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 双指针
双指针分别 i, j 指向 s ts[i] t[j] 时才 i
class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() t.size())return false;int i 0, j 0;for( ; i s.size() j t.size(); j){if(s[i] t[j])i;}return (is.size());}
};2. 二分查找
当有大量的字符串s时应将所有字符的下标存进表里进行二分查找提高效率 二分查找参考
class Solution {int L, R, mid;
public:bool isSubsequence(string s, string t) {if(s.size() t.size())return false;vectorvectorint m(26);//存储t中字符对应的位置int i, j 0;for(i 0; i t.size(); i){m[t[i]-a].push_back(i);//将t对应字符的下标存进数组}for(i 0; i s.size() j t.size(); i){j binarysearch(m[s[i]-a], j);//对s中的字符在对应的t的数组里查找大于等于j的位置if(j -1)//没找到返回错误return false;j;//找到了下次查找开始的位置1}return (is.size());}int binarysearch(vectorint v, int pos)//找值pos的第一个{L 0, R v.size()-1;while(L R){mid L((R-L)1);if(v[mid] pos){if(mid0 || v[mid-1] pos)return v[mid];elseR mid-1;}else if(v[mid] pos)L mid1;}return -1;}
};
