判断子序列

解题思路

双指针操作

'''
思路：双指针操作
1. 首先判断子串S的长度是否大于原串T的长度,若是则无法匹配,直接返回False。
2. 重点：双指针操作。定义一个变量match_s表示匹配到的字符,一个变量ind_S表示子串S的当前索引。然后遍历原串T中的每一个字符,如果该字符与子串S当前索引指向的字符相同,则将该字符加入match_s中,并将ind_S加一。
3. 最后判断match_s是否等于子串S,若是则匹配成功,返回True,否则返回False。
'''
class Solution:
    def isSubsequence(self , S: str, T: str) -> bool:
        # write code here
        if len(S) > len(T):
            return False
        match_s = '' # 匹配到的字符
        ind_S = 0 # 子串S的索引
        for j in T:
            if j == S[ind_S]:
                match_s += j
                ind_S += 1
        if match_s == S:
            return True
        return False

判断字符串子序列-华为OD机试 2022

• 这里有两个abc的子序列满足，取下标较大的，故返回3

解题思路

双指针。如果匹配完一个子串，在循环T中继续重新匹配S，此时S的索引置为0.

python代码

class Solution:
    def isSubsequence(self , S: str, T: str) -> bool:
        # write code here
        last_ind = -1 # 匹配最后一个子串的首字母在T中的索引
        match_s = '' # 匹配到的字符
        ind_S = 0 # 子串S的索引
        flag = 0
        for j in range(len(T)):
            if T[j] == S[ind_S]:
                if flag == 0: # 只有首字母才会保存索引j
                    last_ind = j 
                flag = 1  # 其他时候置为1
                match_s += T[j] 
                ind_S += 1
            if match_s == S:
                flag = 0 # 首字母标志
                ind_S = 0 # 匹配完成一个子串，将子串索引置为0，重新匹配
                
        return last_ind