leedcode-判断子序列

自己写的，有点麻烦

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 第一步先验证s是t的无序子序列
        # 使用字典记录t中每个字符的出现次数
        mydict = dict()
        for i in t:
            if not mydict.get(i):
                mydict[i] = 1
            else:
                mydict[i] += 1

        # 遍历s中的字符，检查其在t中是否出现过且次数充足
        for j in s:
            if not mydict.get(j) or mydict.get(j) == 0:
                return False
            else:
                mydict[j] -= 1
        
        # 下面验证子序列是有序的
        index_li = list()  # 存储s中字符在t中出现的索引位置
        t_li = list(t)  # 将字符串t转换为列表，方便操作
        for k in s:
            if k not in t_li:
                return False
            else:
                index_li.append(t_li.index(k))  # 记录字符在t中的索引位置
                # 将该字符在t中的索引位置及之前的字符替换为相应数量的星号
                t_li[0:t_li.index(k) + 1] = "*" * (t_li.index(k) + 1)
        
        # 验证索引位置是否递增，即s是否为有序子序列
        m = 0
        while m <= len(index_li) - 2:
            if index_li[m] < index_li[m + 1]:
                m += 1
            else:
                return False
        return True

改进了一点 省去了最后判断index_li是否递增的步骤：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 第一步先验证s是t的无序子序列
        mydict = dict()  # 创建一个字典，用于记录t中每个字符的出现次数
        for i in t:
            if not mydict.get(i):
                mydict[i] = 1
            else:
                mydict[i] += 1

        # 遍历s中的字符，检查其在t中是否出现过且次数充足
        for j in s:
            if not mydict.get(j) or mydict.get(j) == 0:
                return False
            else:
                mydict[j] -= 1
        
        # 下面验证子序列是有序的
        index_li = list()  # 存储s中字符在t中出现的索引位置
        t_li = list(t)  # 将字符串t转换为列表，方便操作

        last_index = -1  # 记录上一个字符在t中的索引位置，初始为-1
        for k in s:
            if k not in t_li:
                return False
            else:
                cur_index = t_li.index(k)  # 获取当前字符在t中的索引位置
                t_li[0:cur_index + 1] = "*" * (cur_index + 1)  # 将该字符在t中的索引位置及之前的字符替换为相应数量的星号
                
                # 检查当前字符的索引位置是否大于上一个字符的索引位置
                # 如果不是，则s不是t的有序子序列，返回False
                if cur_index > last_index:
                    last_index = cur_index
                else:
                    return False
        return True

 gpt优化过的，双指针法：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 定义两个指针，分别指向s和t的开头
        s_ptr, t_ptr = 0, 0

        # 遍历t字符串，同时检查s中的字符是否在t中存在
        while t_ptr < len(t) and s_ptr < len(s):
            # 如果s的字符在t中出现，则移动s的指针
            if s[s_ptr] == t[t_ptr]:
                s_ptr += 1
            t_ptr += 1
        
        # 如果s的指针移动到了末尾，则说明s是t的子序列
        return s_ptr == len(s)