字串應用題: 是否為子序列? 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
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
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
題目會給我們兩條已經從小到大排序好的串列,要求我們依照從小到大的順序,合併這兩條串列。
Thumbnail
題目給定兩個字串s和t,t是s隨機打散後的字串,並且在t裡面額外多加了一個字元, 要求我們找出額外多加入的那個字元。
Thumbnail
題目給定兩個字串s和t,t是s隨機打散後的字串,並且在t裡面額外多加了一個字元, 要求我們找出額外多加入的那個字元。
Thumbnail
題目會給定我們兩個字串,一個字串s,另一個字串t 要求我們判段字串s是否為字串t的子序列? (也就是s的每個字元都可以在t裡面找到,而且前後相對順序相同)
Thumbnail
題目會給定我們兩個字串,一個字串s,另一個字串t 要求我們判段字串s是否為字串t的子序列? (也就是s的每個字元都可以在t裡面找到,而且前後相對順序相同)
Thumbnail
題目會給定一個字串,要求我們計算,最長的不重複區間有多長? 不重複區間的定義,就是區間內的每個字元都不相同。
Thumbnail
題目會給定一個字串,要求我們計算,最長的不重複區間有多長? 不重複區間的定義,就是區間內的每個字元都不相同。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News