字串應用題: 是否為子序列? Is Subsequence Leetcode #392

這題的題目在這裡:

題目會給定我們兩個字串，一個字串s，另一個字串t

要求我們判段字串s是否為字串t的子序列?
(也就是s的每個字元都可以在t裡面找到，而且前後相對順序相同)

測試範例:

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?

演算法:

同樣使用到雙指針的技巧，一個從s的頭部開始，另一個從t的頭部開始。

從左到右開始掃描，一次掃描一個字元，

比對s[i] 和 t[j] 是否相同，

如果相同，則i++，j++ 一起往右一格。

如果不同，則i不動，j++。

最後，掃描結束時，如果i = 字串s的長度，代表s的每個字元都可以在t裡面找到，而且前後相對順序相同。也就是說，字串s是字串t的子序列。

程式碼:

class Solution:
　def isSubsequence(self, s: str, t: str) -> bool:
  
　　# two-pointers, one for s, the other for t
　　idx_s, idx_t = 0, 0
  
　　len_s, len_t = len(s), len(t)
　　
　　# linear scan from head
　　while idx_s < len_s and idx_t < len_t:
　　　
　　　if s[idx_s] == t[idx_t]:
　　　　# matched one character
　　　　# s go to next position
　　　　idx_s += 1
　　　
　　　# t go to next position
　　　idx_t += 1

　　# check all character of s are matched
　　return idx_s == len_s

時間複雜度:

O( m + n ) 最大就是字串的長度，當idx_s或idx_t有一個率先抵達終點，則比對流程結束。

空間複雜度:

O(1) 使用到一組雙指針idx_s和idx_t，都是固定尺寸的臨時變數，占用的記憶體空間為常數級別O(1)

Reference:

[1] Several python sol sharing [w/ Comment] — Is Subsequence — LeetCode