# 392. Is Subsequence - LeetCode Best Practices
Visit original link: [392. Is Subsequence - LeetCode Best Practices](https://leetcoder.net/en/leetcode/392-is-subsequence) for a better experience!
LeetCode link: [392. Is Subsequence](https://leetcode.com/problems/is-subsequence), difficulty: **Medium**.
## LeetCode description of "392. Is Subsequence"
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).
**Follow up**: Suppose there are lots of incoming `s`, say `s1, s2, ..., sk` where `k >= 10^9`, and you want to check one by one to see if `t` has its subsequence. In this scenario, how would you change your code?
### [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 <= 10^4`
- `s` and `t` consist only of lowercase English letters.
## Intuition 1
- Define two pointers, initially pointing to the heads of two strings respectively, and reference characters with `t[i]` and `s[j]`.
- During the traversal of `t`, `i` is automatically incremented by 1, and if `t[i] == s[j]`, then `j += 1`.
- If `j >= s.length`, return `true`. If `t` is traversed and still not returned in advance, return `false`.
## Complexity
- Time complexity: `O(N)`.
- Space complexity: `O(1)`.
## Python
```python
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if s == "":
return True
s_index = 0
for i in range(len(t)):
if t[i] == s[s_index]:
s_index += 1
if s_index >= len(s):
return True
return False
```
## C++
```cpp
class Solution {
public:
bool isSubsequence(string s, string t) {
if (s.empty()) {
return true;
}
int s_index = 0;
for (int i = 0; i < t.length(); i++) {
if (t[i] == s[s_index]) {
s_index++;
if (s_index >= s.length()) {
return true;
}
}
}
return false;
}
};
```
## Java
```java
class Solution {
public boolean isSubsequence(String s, String t) {
if (s.isEmpty()) {
return true;
}
int sIndex = 0;
for (int i = 0; i < t.length(); i++) {
if (t.charAt(i) == s.charAt(sIndex)) {
sIndex++;
if (sIndex >= s.length()) {
return true;
}
}
}
return false;
}
}
```
## C#
```csharp
public class Solution
{
public bool IsSubsequence(string s, string t)
{
if (string.IsNullOrEmpty(s))
{
return true;
}
int sIndex = 0;
for (int i = 0; i < t.Length; i++)
{
if (t[i] == s[sIndex])
{
sIndex++;
if (sIndex >= s.Length)
{
return true;
}
}
}
return false;
}
}
```
## Go
```go
func isSubsequence(s string, t string) bool {
if len(s) == 0 {
return true
}
sIndex := 0
for i := 0; i < len(t); i++ {
if t[i] == s[sIndex] {
sIndex++
if sIndex >= len(s) {
return true
}
}
}
return false
}
```
## JavaScript
```javascript
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
if (s.length === 0) {
return true;
}
let sIndex = 0;
for (let i = 0; i < t.length; i++) {
if (t[i] === s[sIndex]) {
sIndex++;
if (sIndex >= s.length) {
return true;
}
}
}
return false;
};
```
## Ruby
```ruby
# @param {String} s
# @param {String} t
# @return {Boolean}
def is_subsequence(s, t)
return true if s.empty?
s_index = 0
t.each_char.with_index do |char, i|
if char == s[s_index]
s_index += 1
return true if s_index >= s.length
end
end
false
end
```
## Other languages
```java
// Welcome to create a PR to complete the code of this language, thanks!
```
## Intuition 2
- Solution 1 is essentially a "dynamic programming" algorithm implemented with rolling variables. It is easy to understand, and the space complexity is reduced to `O(1)`.
- But now, not only do we not reduce the dimension, but we also increase the dimension. It will be more difficult to understand and implement. So why do this thankless task?
Click to view the answer
Because it can handle a more complex scenario (e.g. [583. Delete Operation for Two Strings](583-delete-operation-for-two-strings.md)) that is common in dynamic programming.
Click to view the answer
Of course, but considering that a one-dimensional rolling array is not as easy to understand as a two-dimensional array, and the implementation process is also prone to errors, so here I didn't give the relevant code implementation. If you are interested, you can try it.