1 """ 2 Given a string s and a string t, check if s is subsequence of t. 3 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). 4 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). 5 Example 1: 6 s = "abc", t = "ahbgdc" 7 Return true. 8 Example 2: 9 s = "axc", t = "ahbgdc" 10 Return false. 11 """ 12 """ 13 自强自信题。 14 看到这道题的想法就是 在子串中遍历每个字符， 15 按顺序判断是否在父串中 16 如果在，flag为True，父串变为所匹配字母的下标+1到末尾 17 如果不在，flag为False，跳出循环 18 """ 19 class Solution1(object): 20 def isSubsequence(self, s, t): 21 n = len(s) #子串长度 22 if n == 0: 23 return True 24 flag = False 25 for i in range(n): 26 if s[i] in t: #判断字符是否在t里 27 t = t[t.index(s[i])+1:] #bug没有加1 28 flag = True 29 else: 30 flag = False 31 break #bug没有提前跳出，后面的字符如果匹配成功，最后会是True 32 return flag 33 34 """ 35 解法二：提供一种队列法。与Solution1思想一致。 36 这里用队列十分高级 37 """ 38 class Solution2(object): 39 def isSubsequence(self, s, t): 40 from collections import deque 41 queue = deque(s) #deque模块提供了两端都可以操作的序列， 42 # 这意味着，在序列的前后你都可以执行添加或删除操作 43 for c in t: 44 if not queue: 45 return True 46 if c == queue[0]: # d = deque('12345') 47 queue.popleft() # d.popleft() '1' extendleft 48 return not queue # d.pop() '5' extend 49 50 """ 51 第三种是种双指针法，很重要，许多题目都可以使用 52 双指针要用while循环，单独操作i, j步长，总长度为终止条件 53 """ 54 class Solution3(object): 55 def isSubsequence(self, s, t): 56 slen = len(s) 57 tlen = len(t) 58 i, j = 0, 0 #bug代码 59 while(i < slen and j < tlen): #for i in range(slen): 60 if(s[i] == t[j]): # for j in range(tlen): 61 i += 1 # if s[i] == t[i]: 62 j += 1 63 return i == slen