你中有我 串接字元成為子序列_雙指針應用_Leetcode #2486

更新 發佈閱讀 5 分鐘

題目敘述 Append Characters to String to Make Subsequence

給定兩個字串s和字串t。

請計算最少的字元串接數量是多少,串接在s的尾端,使得t是s的子序列。


測試範例

Example 1:

Input: s = "coaching", t = "coding"
Output: 4
Explanation: Append the characters "ding" to the end of s so that s = "coachingding".
Now, t is a subsequence of s ("coachingding").
It can be shown that appending any 3 characters to the end of s will never make t a subsequence.

最少補上'ding'在s的尾端,使得t是s的子序列​

Example 2:

Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").

不需要額外串接,t已經是s的子序列。​

Example 3:

Input: s = "z", t = "abcde"
Output: 5
Explanation: Append the characters "abcde" to the end of s so that s = "zabcde".
Now, t is a subsequence of s ("zabcde").
It can be shown that appending any 4 characters to the end of s will never make t a subsequence.

最少補上'abcde'在s的尾端,使得t是s的子序列​

約束條件

Constraints:

  • 1 <= s.length, t.length <= 10^5

字串s和字串t的長度都介於1~十萬之間。

  • s and t consist only of lowercase English letters.

字串s和字串t都只會有英文小寫字母。


觀察

子序列不要求連續,只要字元出現的相對次序相同即可

盡可能的匹配,計算s裡面已經有幾個字元可以滿足t的需求


剩下不足的字元數量

= 要串接的字元數量 = t的總長度 - 成功匹配的字元數量


演算法 雙指針

從左到右掃描每個字元,假如s和t有相符的字元,成功匹配的計數器就加一

最後掃描結束時,t的總長度 - 成功匹配的字元數量 就是 ​要串接的字元數量,使得t是s的子序列。


程式碼 雙指針

class Solution:
def appendCharacters(self, s: str, t: str) -> int:

i, j = 0, 0

# Scan each character from left to right
while i < len(s) and j < len(t): # find characters from 't' in 's':

# Match one character, match count of j adds 1
if s[i] == t[j]:
j +=1

# update checking index of s
i += 1

# counting of missing = total length - count of matched
return len(t) - j

複雜度分析

時間複雜度: O( min( len(s), len(t) ) )

從左到右掃描每個字元,如果先抵達s或t其中一段的尾端,則掃描結束。


空間複雜度: O(1)

所用到的都是固定尺寸的臨時變數,為常數級別O(1)。


Reference

[1] Append Characters to String to Make Subsequence - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
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
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
Thumbnail
題目敘述 Merge Nodes in Between Zeros 給定一個鏈結串列,合併非零區間的節點(以加總的方式合併),輸出合併後的鏈結串列。
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
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
Thumbnail
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定我們兩個字串。 第一個是指定順序的字串order。 第二個是輸入字串s。 要求我們依據order給定的順序,重新排列s。 如果出現order中沒有出現的字母,任意位置皆可。 合法答案可能不只一組,輸出其中一種即可。 題目的原文敘述 測試範例 Example
Thumbnail
題目敘述 題目會給定我們兩個字串。 第一個是指定順序的字串order。 第二個是輸入字串s。 要求我們依據order給定的順序,重新排列s。 如果出現order中沒有出現的字母,任意位置皆可。 合法答案可能不只一組,輸出其中一種即可。 題目的原文敘述 測試範例 Example
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定我們一個字串s,要求我們反轉字串s中所有母音字元的順序,並且以字串的形式輸出。 註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U 題目的原文敘述 測試範例 Example 1: Input: s = "hello" Output: "ho
Thumbnail
題目敘述 題目會給定我們一個字串s,要求我們反轉字串s中所有母音字元的順序,並且以字串的形式輸出。 註: 母音字元為a, e, i, o, u 或者 A, E, I, O, U 題目的原文敘述 測試範例 Example 1: Input: s = "hello" Output: "ho
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News