392.判断子序列

LeetCode LeetCode 双指针字符串动态规划

发布时间 : 2000-01-10 03:09

字数:1.1k 阅读 :

评论:

392.判断子序列

392.判断子序列

392.1 题目

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"
输出："y"

提示：

0 <= s.length <= 1000
t.length == s.length + 1
s 和 t 只包含小写字母

392.2 题解

方法一：双指针

思路

使用两个指针分别遍历 s 和 t。如果当前字符相等，移动 s 指针；无论是否相等，都移动 t 指针。最终如果 s 指针到达末尾，说明 s 是 t 的子序列。

核心思想：贪心匹配，按顺序在 t 中找 s 的每个字符。

具体步骤：

初始化双指针 sIndex = 0, tIndex = 0。
遍历字符串 t：
- 如果 s[sIndex] == t[tIndex]：sIndex++
- tIndex++
如果 sIndex == s.Length，返回 true；否则返回 false。

举例：对于 s = "abc", t = "ahbgdc"：

tIndex=0：t[0]='a' == s[0]='a'，sIndex=1
tIndex=1：t[1]='h' != s[1]='b'
tIndex=2：t[2]='b' == s[1]='b'，sIndex=2
tIndex=3：t[3]='g' != s[2]='c'
tIndex=4：t[4]='d' != s[2]='c'
tIndex=5：t[5]='c' == s[2]='c'，sIndex=3
sIndex == s.Length，返回 true

复杂度分析

时间复杂度：O(n + m)，遍历两个字符串。
空间复杂度：O(1)，只使用指针变量。

代码

// 方法一：双指针
// 初始化两个指针,循环遍历字符串 s 和 t,如果 s 和 t 当前位置的字符相等，移动 s 指针,不论是否相等，都移动 t 指针,判断s 指针到达了字符串 s 的末尾
static bool IsSubsequence1(string s, string t)
{
    // 初始化两个指针，分别指向字符串 s 和 t 的起始位置
    int sIndex = 0, tIndex = 0;

    // 循环遍历字符串 s 和 t
    while (sIndex < s.Length && tIndex < t.Length)
    {
        // 如果 s 和 t 当前位置的字符相等，移动 s 指针
        if (s[sIndex] == t[tIndex])
        {
            sIndex++;
        }

        // 不论是否相等，都移动 t 指针
        tIndex++;
    }

    // 如果 s 指针到达了字符串 s 的末尾，说明 s 是 t 的子序列，返回 true；否则，返回 false
    return sIndex == s.Length;
}

392.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
        // 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
        // 进阶：
        // 如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。
        // 在这种情况下，你会怎样改变代码？

        // 示例 1：
        // 输入：s = "abc", t = "ahbgdc"
        // 输出：true

        // 示例 2：
        // 输入：s = "axc", t = "ahbgdc"
        // 输出：false

        // 提示：
        // 0 <= s.length <= 100
        // 0 <= t.length <= 10^4
        // 两个字符串都只由小写字符组成。

        #endregion

        #region 测试

        // 示例 1
        string s1 = "abc";
        string t1 = "ahbgdc";
        bool result1_1 = IsSubsequence1(s1, t1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");

        // 示例 2
        string s2 = "axc";
        string t2 = "ahbgdc";
        bool result2_1 = IsSubsequence1(s2, t2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");

        #endregion
    }

    #region 答案

    // 方法一：双指针
    // 初始化两个指针,循环遍历字符串 s 和 t,如果 s 和 t 当前位置的字符相等，移动 s 指针,不论是否相等，都移动 t 指针,判断s 指针到达了字符串 s 的末尾
    static bool IsSubsequence1(string s, string t)
    {
        // 初始化两个指针，分别指向字符串 s 和 t 的起始位置
        int sIndex = 0, tIndex = 0;

        // 循环遍历字符串 s 和 t
        while (sIndex < s.Length && tIndex < t.Length)
        {
            // 如果 s 和 t 当前位置的字符相等，移动 s 指针
            if (s[sIndex] == t[tIndex])
            {
                sIndex++;
            }

            // 不论是否相等，都移动 t 指针
            tIndex++;
        }

        // 如果 s 指针到达了字符串 s 的末尾，说明 s 是 t 的子序列，返回 true；否则，返回 false
        return sIndex == s.Length;
    }

    #endregion
}

392.4 运行结果

示例1 方法1 输出：True
示例2 方法1 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com