Last Updated on 2022-11-28 by Clay
題目
ou are given two strings s and t consisting of only lowercase English letters.
Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
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.
Example 2:
Input: s = "abcde", t = "a"
Output: 0
Explanation: t is already a subsequence of s ("abcde").
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.
Constraints:
1 <= s.length, t.length <= 105sandtconsist only of lowercase English letters.
題目給定兩個字串（全是小寫字母），然後我們要判斷需要在 s 字串尾端添加多少 t 字串的字元，才能使 s 字串包含的子序列（subsequence）也包含 t 字串。
解題思路
我的想法很單純，分別建立 si 和 ti 兩變數代表著兩個字串當前判斷字元的位置。如果當前 s[si] 跟 t[ti] 一致，則代表這個字元已經存在 s 字串中，則把 si 和 ti 都增加一個數值；反之，若當前判斷的兩字串字元不一致，則僅增加 si，繼續判斷 s 字串的下一個字元。
因為我們總需要讓 t 字串中的字元都出現在 s 字串中，所以沒匹配的 t[ti] 是不能跳過的。
那最後，僅需要返回 t 字串長度 - ti，則可以判斷出我們需要在 s 字串後尚需添加多少字元。
C++ 範例程式碼
class Solution {
public:
int appendCharacters(string s, string t) {
// Init
int si = 0;
int ti = 0;
// Find the same characters
while (si < s.size()) {
if (ti < t.size() && s[si] == t[ti]) {
++ti;
}
++si;
}
// Return the character numbers that need to appending
return t.size() - ti;
}
};Python 範例程式碼
class Solution:
def appendCharacters(self, s: str, t: str) -> int:
si = 0
ti = 0
while (si < len(s) and ti < len(t)):
if s[si] == t[ti]:
si += 1
ti += 1
else:
si += 1
return len(t) - ti