Description

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

1
2

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

1
2

Input: s = "axc", t = "ahbgdc"
Output: false

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s and t consist only of lowercase English letters.

Solutions

Solution 1

Idea: string’s find() function returns the position of a character when it is found, so I continue to search down from that position, so isn’t that a solution?

We iterate through the string s, searching one by one to see if the character is in the string t. If it is, we add an offset to this position and continue searching for the next character.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool isSubsequence(string s, string t) {
        std::string::size_type pos{0};
        for (int i = 0; i < s.size(); ++i) {
            auto ipos = t.find(s[i], pos);
            if (ipos == std::string::npos) {
                return false;
            } else {
                pos = ipos + 1;
            }
        }
        return true;
    }
};

Solution 2

Set double pointers i , j to point to the first character of string s , t respectively, traverse string t :

• When s[i] == t[j], it means the match is successful, then i++ , j++ at the same time; furthermore, if i has gone through the end of s, it means s is a subsequence of t, then it should return true earlier;
• When s[i] ! = t[j], it means the match fails, then only j++ ;
• If after traversing string t, string s is still not traversed, it means s is not a subsequence of t, then return false.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if (s.size() > t.size())
            return false;
        for (int i = 0, j = 0; j < t.size(); j++) {
            if (s[i] == t[j]) {
                // 若已经遍历完 s ，则提前返回 true
                if (++i == s.size())
                    return true;
            }
        }
        return false;
    }
};