Keshawn_lu's Blog

Leetcode 392. 判断子序列

字数统计: 312阅读时长: 1 min
2020/07/27 Share

题目简介:

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

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

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

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

返回 true.

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

返回 false.

思路:

记录每次找到字符时的位置,则寻找下一个字符时,从上一个字符寻找到的位置的后一个位置开始,若找不到,则返回false。若每个字符都能找到,则返回true

tips:

  • s为空时,返回true
  • 学会运用find()函数。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
bool isSubsequence(string s, string t) {

vector<int> pos(s.size());

if(s.empty())
return true;

pos[0] = t.find(s[0]);

if(pos[0] == t.npos)
return false;

for(int i = 1; i < s.size(); i++){

pos[i] = t.find(s[i], pos[i - 1] + 1);

if(pos[i] == t.npos)
return false;
}

return true;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: