392. Is Subsequence

[songyy5517]

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:

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

Example 2:

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

Analysis This problem is similar to 334. Increasing Triplet Subsequence , where we also need to apply the idea of Greedy algorithm. Specifically, in order to match the string as many as possible, we have to match the character in the subsequence string as soon as possible. For example, say s: bxxxxbca, t: bca , we should match the first b instead of the later one. Therefore, we can set two pointers pointer at the beginning of the two strings. Next, scan these two strings, only move the pointer of the subseq string if can match.

[songyy5517]

Approach: Greedy & Two pointers

1. Exception handling;
2. Define pointer ps pointing at the beginning of string s;
3. Loop through string t and match s[ps] and t[pt]:
   • If they can match, move ps to the next position;
   • If ps reaches the end of string s, then return true.
4. Otherwise, the string s is not fully matched, then return false.

Complexity Analysis

• Time complexity: $O(N)$ , where $N$ is the length of string t, travarsing string t takes $O(N)$ time;
• Space complexity: $O(1)$ , additionally define constant-sized variables.

[songyy5517]

class Solution {
    public boolean isSubsequence(String s, String t) {
        // 思路：指针 & 贪心算法。
        // 依次将字符串s的字符与t中的字符进行匹配，每次匹配成功后将指针ps向后移动。
        // 遍历完成后，根据ps是否到达s的最后判断是否为子串。
        // 1. 异常处理
        if (s.length() == 0)
            return true;

        // 2. 定义双指针
        int ps = 0;

        for (int i = 0; i < t.length(); i++){
            if (s.charAt(ps) == t.charAt(i)){
                if (++ps == s.length())
                    return true;
            }
        }

        return false;
    }
}

[songyy5517]

2024/5/10

• 贪心算法的思想不太熟练。这种需要找有顺序的子序列的题目（392/334）都可以使用贪心算法来解决。