Leetcode 392 - Is Subsequence

題目

Problem#

給兩個字串 s 和 t 問 s 是不是 t 的子序列(Subsequence)

• 0 <= s.length <= 100
• 0 <= t.length <= 104

Follow-up: 當 s.length >= 10^9 時要怎麼做

想法#

當下想到 DP 的作法，看 s 和 t 的 LCS 長度是否跟 s.length() 一樣就好，$\mathcal{O}(NM)$
另一個做法就是雙指標直接看 s 是否都在 t 裏頭就好 $\mathcal{O}(N+M)$

N=s.length, M=t.length

AC Code#

賞析#

• 只有三行的雙指標
  • https://leetcode.com/problems/is-subsequence/discuss/87272/3-lines-C

心得#

看到 subsequence 直覺就想到 LCS 但題目好像不是問這個