0392. Is Subsequence

# 392. Is Subsequence#

## 题目 #

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and tt is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `"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
``````

Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits: Special thanks to  @pbrother for adding this problem and creating all test cases.

## 解题思路 #

• 给定 2 个字符串 s 和 t，问 s 是不是 t 的子序列。注意 s 在 t 中还需要保持 s 的字母的顺序。
• 这是一题贪心算法。直接做即可。

## 代码 #

``````
package leetcode

// 解法一 O(n^2)
func isSubsequence(s string, t string) bool {
index := 0
for i := 0; i < len(s); i++ {
flag := false
for ; index < len(t); index++ {
if s[i] == t[index] {
flag = true
break
}
}
if flag == true {
index++
continue
} else {
return false
}
}
return true
}

// 解法二 O(n)
func isSubsequence1(s string, t string) bool {
for len(s) > 0 && len(t) > 0 {
if s == t {
s = s[1:]
}
t = t[1:]
}
return len(s) == 0
}

`````` Apr 8, 2023 Edit this page