C++ 判断子序列算法详解：双指针法实现与优化

问题定义

给定两个字符串 s 和 t，判断 s 是否为 t 的子序列。子序列的定义是：原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。例如，"ace" 是 "abcde" 的子序列，而 "aec" 不是。

约束条件：

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

第1步：理解双指针策略

核心思想是使用两个指针分别指向字符串 s 和 t 的起始位置。我们依次遍历 t，尝试按顺序匹配 s 中的字符。只要 s 中的所有字符都能在 t 中找到且保持原有顺序，则返回 true；否则返回 false。

第2步：C++ 代码实现

以下是使用 C++ 实现的完整解法。相比其他语言版本，C++ 直接操作 `std::string` 或字符数组，效率更高。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i = 0; // 指向 s 的指针
        int j = 0; // 指向 t 的指针
        
        // 遍历 t，尝试匹配 s 中的每个字符
        while (i < s.length() && j < t.length()) {
            if (s[i] == t[j]) {
                // 如果当前字符匹配，s 的指针向后移
                i++;
            }
            // t 的指针始终向后移，无论是否匹配
            j++;
        }
        
        // 如果 i 等于 s 的长度，说明 s 的所有字符都已在 t 中找到
        return i == s.length();
    }
};

实例验证

我们可以通过以下测试用例验证算法的正确性：

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

解释：'a' 在 t[0]，'b' 在 t[1]，'c' 在 t[3]，顺序正确。

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

解释：虽然 'a' 和 'c' 都在 t 中存在，但 'x' 不在 t 中，故无法构成子序列。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 t 的长度。我们需要遍历一次 t。
• 空间复杂度：O(1)，仅使用了两个整型变量作为指针，无需额外空间。

图1：算法执行流程示意

总结

通过双指针法，我们可以简洁高效地解决子序列判断问题。该方法逻辑清晰，易于实现，是处理此类字符串匹配问题的首选方案。以上就是 C++ 判断子序列题目的详细内容，更多关于 C++ 算法技巧的资料请关注本站其它相关文章！