You 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 <= 105
s
andt
consist only of lowercase English letters.
追加字符以获得子序列。
给你两个仅由小写英文字母组成的字符串 s 和 t 。
现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ,返回需要追加的最少字符数。
子序列是一个可以由其他字符串删除部分(或不删除)字符但不改变剩下字符顺序得到的字符串。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/append-characters-to-string-to-make-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路是双指针。这是判断子序列的基本题,我们用两个指针 i, j 分别指向 s 和 t 并同时开始遍历。当 s 遍历完的时候,如果 t 也遍历完了,说明 t 本身就是 s 的子序列,否则需要补足的字母个数 = n - j。
时间O(m) - s 的长度
空间O(1)
Java实现
1 class Solution { 2 public int appendCharacters(String s, String t) { 3 int m = s.length(); 4 int n = t.length(); 5 int i = 0; 6 int j = 0; 7 while (i < m && j < n) { 8 if (s.charAt(i) == t.charAt(j)) { 9 j++; 10 } 11 i++; 12 } 13 if (j == n) { 14 return 0; 15 } 16 return n - j; 17 } 18 }
- Subsequence Characters LeetCode Append Stringsubsequence characters leetcode append characters leetcode string extra characters substrings unique string characters leetcode formed words characters substring repeating leetcode subsequence arithmetic difference leetcode characters leetcode stream 1032 subsequence leetcode maximum score leetcode largest number string difference leetcode string 2451