贪心
双指针
字符串
题目描述
给你两个仅由小写英文字母组成的字符串 s
和 t
。
现在需要通过向 s
末尾追加字符的方式使 t
变成 s
的一个 子序列 ,返回需要追加的最少字符数。
子序列是一个可以由其他字符串删除部分(或不删除)字符但不改变剩下字符顺序得到的字符串。
示例 1:
输入: s = "coaching", t = "coding"
输出: 4
解释: 向 s 末尾追加字符串 "ding" ,s = "coachingding" 。
现在,t 是 s ("co achingding ") 的一个子序列。
可以证明向 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 ("zabcde ") 的一个子序列。
可以证明向 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$ 的长度。
Python3 Java C++ Go TypeScript
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13 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 ;
}
GitHub