Skip to content

392. Is Subsequence

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:

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?

Solutions

Solution 1: Two Pointers

We define two pointers \(i\) and \(j\) to point to the initial position of the string \(s\) and \(t\) respectively. Each time we compare the two characters pointed to by the two pointers, if they are the same, both pointers move right at the same time; if they are not the same, only \(j\) moves right. When the pointer \(i\) moves to the end of the string \(s\), it means that \(s\) is the subsequence of \(t\).

The time complexity is \(O(m + n)\), where \(m\) and \(n\) are the lengths of the strings \(s\) and \(t\) respectively. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length(), n = t.length();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s.charAt(i) == t.charAt(j)) {
                ++i;
            }
            ++j;
        }
        return i == m;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool isSubsequence(string s, string t) {
        int m = s.size(), n = t.size();
        int i = 0, j = 0;
        for (; i < m && j < n; ++j) {
            if (s[i] == t[j]) {
                ++i;
            }
        }
        return i == m;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func isSubsequence(s string, t string) bool {
    i, j, m, n := 0, 0, len(s), len(t)
    for i < m && j < n {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == m
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function isSubsequence(s: string, t: string): boolean {
    const m = s.length;
    const n = t.length;
    let i = 0;
    for (let j = 0; i < m && j < n; ++j) {
        if (s[i] === t[j]) {
            ++i;
        }
    }
    return i === m;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn is_subsequence(s: String, t: String) -> bool {
        let (s, t) = (s.as_bytes(), t.as_bytes());
        let n = t.len();
        let mut i = 0;
        for &c in s.iter() {
            while i < n && t[i] != c {
                i += 1;
            }
            if i == n {
                return false;
            }
            i += 1;
        }
        true
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class Solution {
    public bool IsSubsequence(string s, string t) {
        int m = s.Length, n = t.Length;
        int i = 0, j = 0;
        for (; i < m && j < n; ++j) {
            if (s[i] == t[j]) {
                ++i;
            }
        }
        return i == m;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
bool isSubsequence(char* s, char* t) {
    int m = strlen(s);
    int n = strlen(t);
    int i = 0;
    for (int j = 0; i < m && j < n; ++j) {
        if (s[i] == t[j]) {
            ++i;
        }
    }
    return i == m;
}

Comments