【leetcode面试经典150题】26.判断子序列（C++）

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主，题解使用C++语言。（若有使用其他语言的同学也可了解题解思路，本质上语法内容一致）

【题目描述】

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

【示例一】

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

【示例二】

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

【提示及数据范围】

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

【代码】

// 方法一：双指针

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == n;
    }
};


// 方法二：队列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        queue<char> q;
        for(auto& c : s){
            q.push(c);
        }
        for(auto& c : t){
            if(c == q.front()) q.pop();
        }
        return q.empty();
    }
};