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).

Q: 判断字符串s是否是字符串t的子序列?

(注意:问的是子序列不是子串,子序列中元素不一定相邻,子串中元素则必须相邻。)

Constraints:

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

Example 1:

  1. Input: s = "abc", t = "ahbgdc"
  2. Output: true

Example 2:

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

解法1 直接比较(最快的)

class Solution {
public:
    bool isSubsequence(string s, string t) {
        /* s中的字符在t中可能是分散、重复的,但相对顺序一定是递增的。
         * 定义count表示s中的字符在t中已出现的个数,
         * 遍历t,如果下一个字符和s[count]一致,比较s和t的下一个字符(count++);
         *       否则继续往下遍历t;
         * 直到count=s.length()(是子序列)或者t遍历完毕(不是子序列)。
         * 
         * 复杂度O(t.length())
         */
        if(s.length() == 0){
            return true;           // 空s的是任何t的子序列
        }
        else if(t.length() == 0){
            return false;          // s不空,t空,肯定不是
        }

        int count=0, i=0;
        for(int i=0; i<t.length(); i++){
            if(s[count] == t[i]){
                count++;
            }
            if(count >= s.length()){
                return true;
            }
        }
        return false;
    }
};

运行效率评价
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Is Subsequence.
Memory Usage: 6.5 MB, less than 34.43% of C++ online submissions for Is Subsequence.

解法2 动态规划

class Solution {
public:
    // 动态规划,复杂度O(m*n)
    bool isSubsequence(string s, string t) {
        // s和t的最长公共子序列的长度如果等于s的长度,那么s就是t的子序列
        if(s.length() == 0){
            return true;           // 空s的是任何t的子序列
        }
        else if(t.length() == 0){
            return false;          // s不空,t空,肯定不是
        }
        else{
            return this->lengthOfLongestCommonSequence(s, t) == s.length();
        }
    }

    int lengthOfLongestCommonSequence(string& s, string& t){
        // 动态规划求最长公共子序列的长度,不需要记录方向信息
        int m=s.length(), n=t.length();
        vector<vector<int>> dpArray(m+1, vector<int>(n+1, 0));
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(s[i-1] == t[j-1]){
                    dpArray[i][j] = dpArray[i-1][j-1] + 1;
                }
                else{
                    dpArray[i][j] = max(dpArray[i-1][j], dpArray[i][j-1]);
                }
            }
        }
        return dpArray[m][n];
    }
};

运行效率评价:
Runtime: 4 ms, faster than 28.25% of C++ online submissions for Is Subsequence.
Memory Usage: 8 MB, less than 9.05% of C++ online submissions for Is Subsequence.