### 题目

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example 1:

s = "abc", t = "ahbgdc"

Return true.


Example 2:

s = "axc", t = "ahbgdc"

Return false.


• If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

### 两个指针

sp                  tp
|                   |
a,b,c               a,h,b,g,d,c

a和a匹配上了，同时右移，
sp                  tp
|                   |
a,b,c               a,h,b,g,d,c

b和h没有匹配上，只有tp右移，
sp                  tp
|                   |
a,b,c               a,h,b,g,d,c


#### 代码

class Solution {
public boolean isSubsequence(String s, String t) {
if (s == null || t == null) {
return false;
}
int sp = 0, tp = 0;
while (sp < s.length() && tp < t.length()) {
if (s.charAt(sp) == t.charAt(tp)) {
sp++;
}
tp++;
}
return sp == s.length();
}
}


#### 结果

t的长度远远大于s的情况下，采取在t中查询s中字符的策略，比完整遍历t要更有效。在字符串中查询某个字符可以用基于二分查找的String.indexOf()函数，

public int indexOf(String str, int fromIndex)

                 fromIndex
|                   |
a,b,c               a,h,b,g,d,c

fromIndex
|                   |
a,b,c               a,h,b,g,d,c


#### 代码

class Solution {
public boolean isSubsequence(String s, String t) {
if (s == null || t == null) {
return false;
}
char c = 0;
int prev = 0;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
prev = t.indexOf(c, prev);
if (prev < 0) {
return false;
}
prev++;
}
return true;
}
}