Is Subsequence

Problem Statement

In this problem, you are provided with two strings: s and t. The task is to determine whether the string s is a subsequence of the string t. The function should return true if s is a subsequence of t, and false otherwise.

To clarify, a subsequence is derived from another string by deleting some or none of the characters without rearranging the order of the remaining characters. For instance, "ace" is a subsequence of "abcde" because you can remove "b" and "d" from "abcde" to form "ace". However, "aec" is not a subsequence of "abcde" since the letters are not in the same order in both strings.

Examples

Example 1

Input:

s = "abc", t = "ahbgdc"

Output:

true

Example 2

Input:

s = "axc", t = "ahbgdc"

Output:

false

Constraints

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

Approach and Intuition

To solve the problem of determining if s is a subsequence of t, the key is to check each character of s and ensure it appears in t in the same relative order. If any character in s fails this condition, the function will return false. Below is a step-by-step approach to realize the solution:

1. Initialize a pointer for string s at position 0.
2. Iterate through each character of string t.
   • For each character in t, compare it with the character at the current pointer position of s.
   • If they match:
     • Move the pointer forward in s (i.e., increment the pointer).
     • If the pointer equals the length of s, it means all characters of s have been matched in t in order, so return true.
3. If the end of t is reached and there are characters in s that haven't been matched, return false.

This approach ensures a linear time complexity relative to the length of t, making it efficient given the constraint where the length of t can be up to 10,000. Each character of t is processed in sequence, and the process halts early if s is fully matched or continues to the end of t if needed.

Solutions

class Solution {
    
    public boolean sequenceMatcher(String str1, String str2) {
    
        Integer len1 = str1.length(), len2 = str2.length();
        if (len1 == 0)
            return true;
    
        int[][] matchTable = new int[len1 + 1][len2 + 1];
        for (int j = 1; j <= len2; ++j) {
            for (int i = 1; i <= len1; ++i) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    matchTable[i][j] = matchTable[i - 1][j - 1] + 1;
                else
                    matchTable[i][j] = Math.max(matchTable[i][j - 1], matchTable[i - 1][j]);
            }
            if (matchTable[len1][j] == len1)
                return true;
        }
            
        return false;
    }
}