LeetCode 392.判断子序列(C++)

这道题目考察的是动态规划，实际上就是需要把大问题分解成一个个的子问题。

要想找到子序列s在长序列t中是否存在，那么就可以分解为，找子序列s的每一个字符是否在长序列t中依次存在。

查找失败的情况（返回false）：

如果找完了整个长序列t，还没有遍历完s就说明不存在，因此就需要判断是否到了长序列t的末尾。

如果在子序列s中任意一个字符，长序列t中没有，同样也说明查找失败。

查找成功的情况（返回true）：

循环完了，没有返回失败就代表查找成功了

下面直接上代码：

class Solution {
public:
    bool isSubsequence(string s, string t) {

        // last_pos 用于记录上一次查找的位置，初始化为0
        size_t last_pos = 0;

        // 遍历整个子序列s
        for (size_t i = 0; i < s.size(); ++i)
        {
            // 这里就是失败的两个条件
            if ((last_pos == t.size()) || (t.find(s[i], last_pos) == t.npos))
                return false;
            
            // 如果当前字符找到了，就把找到的下一个位置赋给last_pos
            else
                last_pos = t.find(s[i], last_pos) + 1;
        }
        return true;
    }
};

• 18/18 cases passed (0 ms)
• Your runtime beats 100 % of cpp submissions
• Your memory usage beats 78.61 % of cpp submissions (6.2 MB)