Leetcode 判断子序列

通过双指针来判断字符串s是否是字符串t的子序列。

算法思想：

1. 双指针法：

   • 我们使用两个指针i和j分别遍历字符串s和t。
   • 初始时，i指向s的第一个字符，j指向t的第一个字符。

2. 匹配字符：

   • 每次比较s[i]和t[j]：
     • 如果s[i] == t[j]，说明s当前字符与t当前字符匹配，接下来可以继续匹配s的下一个字符，所以指针i右移。
     • 不论是否匹配成功，指针j都会右移，因为需要继续在t中查找。

3. 判断结果：

   • 循环结束后，我们检查i是否等于s的长度（i == s.length()）。如果i等于s的长度，说明s的所有字符都能在t中按顺序找到，s是t的子序列，返回true。否则返回false。

代码解读：

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sLen = s.length(), tLen = t.length();  // 获取字符串 s 和 t 的长度
        int i = 0, j = 0;  // 初始化双指针，i 指向 s 的第一个字符，j 指向 t 的第一个字符
        
        // 当 i 小于 s 的长度 且 j 小于 t 的长度时进行遍历
        while (i < sLen && j < tLen) {
            if (s.charAt(i) == t.charAt(j)) {  // 如果 s[i] == t[j]，则匹配，i 右移
                i++;
            }
            j++;  // j 每次都右移，遍历 t
        }
        
        // 如果 i == s 的长度，说明 s 的所有字符都按顺序匹配到了 t 中
        return i == sLen;
    }
}

复杂度分析：

• 时间复杂度: O(n)，其中 n 是字符串 t 的长度。因为我们只需遍历一次 t。
• 空间复杂度: O(1)，只用了常量级别的额外空间来存储指针。

总结：这个算法通过双指针逐步在t中匹配s的字符，如果i能够遍历完s，则说明s是t的子序列。

为什么使用while循环而不是for循环？

在这个问题中，使用while循环而不是for循环的原因主要是因为我们需要两个指针（i 和 j）来分别遍历两个不同的字符串（s 和 t），并且它们的移动并不是严格同步的。具体来说，i 和 j 的移动取决于匹配条件，因此使用 while 循环更直观和灵活。

具体原因如下：

1. 两个指针的独立性：

   • i 和 j 这两个指针的移动是独立的。只有当 s[i] == t[j] 时，i 才会移动，而 j 每次都要移动。因此，两个指针的移动节奏不一样，而 while 循环允许我们灵活地控制指针移动的逻辑。
   • 如果用 for 循环的话，通常是在一个固定范围内逐个递增，比较适合单个序列的遍历，而不太方便这种条件控制的多序列匹配。

2. 终止条件的灵活性：

   • while 循环的终止条件可以是两个字符串长度中的较大者。我们只要确保在 i < s.length() 和 j < t.length() 的范围内操作即可。只要有一个条件不满足，就可以退出循环。这样的控制对于不同的字符串长度非常合适。
   • 如果用 for 循环，虽然也可以实现，但写法上会比较冗长，比如需要分别写两个嵌套的循环或者额外的判断条件，增加了代码的复杂度。

3. 代码可读性：

   • while 循环更自然地表达了“当两个字符串都没有遍历完时，继续匹配”的逻辑。它更加直观地反映了我们对字符匹配的意图，即逐个对比字符，遇到匹配的就移动 i，无论是否匹配都要移动 j，直到遍历结束。
   • for 循环一般用于每次都需要固定增加步数的场景，但在这里，我们不需要 i 和 j 同时增加，这让 while 循环更容易理解。

for 循环的实现：

虽然使用 while 循环更加直观，但实际上也可以使用 for 循环实现类似逻辑。示例如下：

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sLen = s.length();
        int j = 0;  // 只需要为 t 使用 for 循环，s 由条件控制

        for (int i = 0; i < t.length() && j < sLen; i++) {
            if (t.charAt(i) == s.charAt(j)) {
                j++;  // 如果匹配，移动 s 的指针 j
            }
        }

        return j == sLen;  // 判断是否 s 的所有字符都匹配
    }
}

总结：

• while 循环 更加适合这个场景，因为它能够灵活控制两个指针的移动和终止条件，代码简洁易读。
• for 循环 也可以实现相同的功能，但写起来相对不太直观，代码逻辑上可能会稍微复杂一些。