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

更新於 發佈於 閱讀時間約 3 分鐘
raw-image

這題的題目在這裡:

題目會給定我們兩個字串,一個字串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

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/06
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/10/01
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
2024/09/29
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
Thumbnail
看更多
你可能也想看
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
Append Characters to String to Make Subsequence 給定兩個字串s和字串t。 請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。 測試範例 Example 1: Input: s = "coaching", t =
Thumbnail
Append Characters to String to Make Subsequence 給定兩個字串s和字串t。 請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。 測試範例 Example 1: Input: s = "coaching", t =
Thumbnail
題目敘述 題目會給我們兩個輸入,字串s和字串t,要求我們判定s是否為t的子序列(Subsequence)? 題目的原文敘述 測試範例 Example 1: Input: s = "abc", t = "ahbgdc" Output: true Example 2: Input:
Thumbnail
題目敘述 題目會給我們兩個輸入,字串s和字串t,要求我們判定s是否為t的子序列(Subsequence)? 題目的原文敘述 測試範例 Example 1: Input: s = "abc", t = "ahbgdc" Output: true Example 2: Input:
Thumbnail
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
Thumbnail
題目敘述 題目會給我們一個輸入字串s,題目還保證字串s的長度一定是偶數。 要求我們判定字串s的前半部和後半部是否相似? 在本題中,兩個字串相似的定義為兩個字串都擁有相同的母音英文字母: 註: 母音英文字母為a, e, i, o, u, A, E, I, O, U 題目的原文敘述 測試
Thumbnail
題目會給我們一個字串陣列nums,內容都是二進位字串,要求我們造出一個另一個相等長度,新的二進位字串,而且不和字串陣列nums內的重複。 答案可能有不只一組,回傳合任一組合法的答案皆可。
Thumbnail
題目會給我們一個字串陣列nums,內容都是二進位字串,要求我們造出一個另一個相等長度,新的二進位字串,而且不和字串陣列nums內的重複。 答案可能有不只一組,回傳合任一組合法的答案皆可。
Thumbnail
題目會給定我們一個字串s,要求我們計算出同質子字串有幾個? 同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。
Thumbnail
題目會給定我們一個字串s,要求我們計算出同質子字串有幾個? 同質子字串的定義就是子字串內部的字元都相同,例如a, aa, aaa, ... 等等這些就是同質子字串。
Thumbnail
題目會給定兩個字串s,t,把裡面的井字號#視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部依照規則處理完以後,s,t剩下的字串內容兩者是否相等?
Thumbnail
題目會給定兩個字串s,t,把裡面的井字號#視為鍵盤上的backspace,往前(往左方)吃掉最靠近的字元。 請位最後全部依照規則處理完以後,s,t剩下的字串內容兩者是否相等?
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News