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

Zel Ribeiro on Unsplash

題目敘述 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