Question

2486. 追加字符以获得子序列

English Version

题目描述

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

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

解法

方法一：双指针

我们定义两个指针 $i$ 和 $j$，分别指向字符串 $s$ 和 $t$ 的首字符。遍历字符串 $t$，当 $s[i] \neq t[j]$ 时，指针 $i$ 后移，直到 $s[i] = t[j]$ 或者 $i$ 到达字符串 $s$ 的末尾。如果 $i$ 到达字符串 $s$ 的末尾，说明 $t$ 中的字符 $t[j]$ 无法在 $s$ 中找到对应的字符，返回 $t$ 中剩余的字符数。否则，将指针 $i$ 和 $j$ 同时后移，继续遍历字符串 $t$。

时间复杂度 $(m + n)$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。

class Solution:
  def appendCharacters(self, s: str, t: str) -> int:
    i, m = 0, len(s)
    for j, c in enumerate(t):
      while i < m and s[i] != c:
        i += 1
      if i == m:
        return len(t) - j
      i += 1
    return 0

class Solution {
  public int appendCharacters(String s, String t) {
    int m = s.length(), n = t.length();
    for (int i = 0, j = 0; j < n; ++j) {
      while (i < m && s.charAt(i) != t.charAt(j)) {
        ++i;
      }
      if (i++ == m) {
        return n - j;
      }
    }
    return 0;
  }
}

class Solution {
public:
  int appendCharacters(string s, string t) {
    int m = s.size(), n = t.size();
    for (int i = 0, j = 0; j < n; ++j) {
      while (i < m && s[i] != t[j]) {
        ++i;
      }
      if (i++ == m) {
        return n - j;
      }
    }
    return 0;
  }
};

func appendCharacters(s string, t string) int {
  m, n := len(s), len(t)
  for i, j := 0, 0; j < n; i, j = i+1, j+1 {
    for i < m && s[i] != t[j] {
      i++
    }
    if i == m {
      return n - j
    }
  }
  return 0
}

function appendCharacters(s: string, t: string): number {
  const [m, n] = [s.length, t.length];
  for (let i = 0, j = 0; j < n; ++j) {
    while (i < m && s[i] !== t[j]) {
      ++i;
    }
    if (i === m) {
      return n - j;
    }
    ++i;
  }
  return 0;
}