【leetcode面试经典150题】26.判断子序列（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();
    }
};