题目: https://leetcode-cn.com/problems/is-subsequence/
给定字符串 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 的子序列. 在这种情况下, 你会怎样改变代码?
代码:
- class Solution {
- public:
- vector<int> memo[26];
- bool isSubsequence(string s, string t) {
- for(int i = 0;i <t.size();++i)
- memo[t[i] - 'a'].push_back(i);
- int u = -1;
- for(auto p : s){
- int l = 0, r = memo[p - 'a'].size() - 1;
- if(r < 0) return false;
- while(l < r){
- int mid = (l + r)>> 1;
- if(memo[p - 'a'][mid]> u) r = mid;
- else l = mid + 1;
- }
- if(memo[p - 'a'][l] <= u) return false;
- u = memo[p - 'a'][l];
- }
- return true;
- }
- };
- View Code
来源: http://www.bubuko.com/infodetail-3433916.html