LeetCode 0392. Is Subsequence Solution in Java, C++, Python & More | Explanation + Code

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

PythonJavaC++GoTypeScriptRustC#C

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)(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)

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; } }(code-box)

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; }(code-box)