LeetCode题目笔记——2486. 追加字符以获得子序列

这个是上周末的周赛题目，当时忘做了，晚上的时候才想起，可惜了，题目还挺有意思的，类似的好像在以前做过，题目联机在这题目链接

题目描述

给你两个仅由小写英文字母组成的字符串 s 和 t 。

现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。

子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。

示例1：

输入：s = “coaching”, t = “coding”
输出：4
解释：向 s 末尾追加字符串 “ding” ，s = “coachingding” 。
现在，t 是 s (“coachingding”) 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。

示例2：

输入：s = “abcde”, t = “a”
输出：0
解释：t 已经是 s (“abcde”) 的一个子序列。

示例3：

输入：s = “z”, t = “abcde”
输出：5
解释：向 s 末尾追加字符串 “abcde” ，s = “zabcde” 。
现在，t 是 s (“zabcde”) 的一个子序列。
可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。

提示：

1 <= s.length, t.length <= 105
s 和 t 仅由小写英文字母组成

题目难度——中等

方法一：一次遍历

  题目要求往s末尾添加字符来让t成为s的子字符串，那么最简单的方法不就是直接把t往s后面一连不就行了？但这题不行，因为要求是要添加最少数量的字符，那么，我们只需要找到在字符串t中第一个不在s中的字符x，然后把从x到最后的子字符串连到s末尾，不就可以了吗。所以，我们可以一次遍历两个字符串，使用两个指针分别指向他们的位置，每次迭代都把指向s的往后移一个位置，只有s和t当前位置的字符一样的时候才移动t的指针。

代码/C++

class Solution {
public:
    int appendCharacters(string s, string t) {
        int ps = 0, pt = 0;
        while(ps < s.size() && pt < t.size()){
            if(s[ps] == t[pt]){
                pt++;
            }
            ps++;
        }
        return t.size() - pt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

  这个16ms挺慢的，应该更快才对。这种方法的循环次数是长度较小的那个字符串的长度，所以时间是O(N)，只用到了两个常数变量，所以空间是O(1)。。