392. Is Subsequence

  • 44.2%

https://leetcode.com/problems/is-subsequence/

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).

1
2
3
4
5
6
7
8
9
Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:

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?


方法一:

常规动态规划

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size(), n = t.size();
if(m>n)
return false;
if(m==0)
return true;
vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
for(int i=0; i<=n; i++)
dp[0][i] = true;
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
dp[i][j] = dp[i][j-1] || s[i-1]==t[j-1] && dp[i-1][j-1];
return dp[m][n];
}
};

方法二:

双指针,贪心

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isSubsequence(string s, string t) {
int sn = s.size(), tn = t.size();
if(sn==0) return true;
if(sn>tn) return false;
int si = 0, ti = 0;
while(ti<tn){
if(s[si]==t[ti])
si++;
ti++;
if(si==sn)
return true;
}
return false;
}
};

https://discuss.leetcode.com/topic/57147/straight-forward-java-simple-solution/2

Just use two pointers:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public boolean isSubsequence(String s, String t) {
if (s.length() == 0) return true;
int indexS = 0, indexT = 0;
while (indexT < t.length()) {
if (t.charAt(indexT) == s.charAt(indexS)) {
indexS++;
if (indexS == s.length()) return true;
}
indexT++;
}
return false;
}
}

python

https://discuss.leetcode.com/topic/57100/2-lines-python

Just testing whether all characters in s are also in t (in order).

Based on falsetru’s code on StackOverflow which I improved a while ago, see here.

http://stackoverflow.com/questions/24017363/how-to-test-if-one-string-is-a-subsequence-of-another/24017747#24017747

1
2
3
def isSubsequence(self, s, t):
t = iter(t)
return all(c in t for c in s)

https://discuss.leetcode.com/topic/57718/easy-to-understand-binary-search-solution

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
26
27
28
29
from collections import defaultdict
from bisect import bisect_left
class Solution(object):

def createMap(self, s):
# create a map. key is char. value is index of apperance in acending order.
posMap = defaultdict(list)
for i, char in enumerate(s):
posMap[char].append(i)
return posMap


def isSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
posMap = self.createMap(t)
# lowBound is the minimum index the current char has to be at.
lowBound = 0
for char in s:
if char not in posMap: return False
charIndexList = posMap[char]
# try to find an index that is larger than or equal to lowBound
i = bisect_left(charIndexList, lowBound)
if i == len(charIndexList): return False
lowBound = charIndexList[i] + 1
return True
谢谢你,可爱的朋友。