Last Updated on 2022-03-02 by Clay
題目
Given two stringss
andt
, returntrue
ifs
is a subsequence oft
, orfalse
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
andt
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?
題目輸入兩個字串 s
和 t
,我們要判斷 t
刪減字元後是否可以還原成 s
。
解題思路
由於最近在忙面試,比較沒時間慢慢解...... 今天也就直接放了個非最佳解的 two-points 解法。
我知道存在著 DP 解,已經看過討論區了 XD
C++ 範例程式碼
class Solution {
public:
bool isSubsequence(string s, string t) {
// Base case
if (s.empty()) return true;
// Init
int si = 0;
// Match
for (int ti=0; ti<t.size(); ++ti) {
if (s[si] == t[ti]) {
++si;
}
if (si == s.size()) return true;
}
return false;
}
};
Python 範例程式碼
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# Base case
if not s: return True
# Init
si = 0
# Match
for ti in range(len(t)):
if s[si] == t[ti]:
si += 1
if si == len(s): return True
return False