Leetcode 75: Day 2: 392. Is Subsequence

Question:

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

Constraints:

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

Follow up: Suppose there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Solution:

  • Keep a pointer j that will point at the characters in s string.
  • If length of s string is greater than t, return false as subsequence is not possible.
  • Iterate over the characters in t string.
  • If any character at ith position matches the character at jth position in s string, increment j, provided j is smaller than length of s.
  • At the end, if j is not equal to the length of the s string, return false, else return true.

Code:


class Solution {
    public boolean isSubsequence(String s, String t) {

        if(s.length() > t.length()) return false;

        int j = 0;

        for(int i = 0; i < t.length(); i++){

            if(j < s.length() && t.charAt(i) == s.charAt(j)){
                j++;
            }

        }

        if(j != s.length()) return false;

        return true;

    }
}

Complexity:

  • Time: O(N)
  • Space: O(1)