企业官网建设流程全解析

2026-10-08：一次替换后的子序列。用go语言，给定两个只包含小写字母的字符串 s 和 t。你可以在 s 中至多改动一个位置上的字符，把它换成任意一个小写字母。问经过这样的至多一次改动后，能否让 s 按原有先后顺序出现在 t 中。也就是说，能否从 t 里删掉一些字符后，得到完整的 s；只要求字符顺序一致，不要求连续。如果能够做到，结果为 true；否则为 false。

1 <= s.length, t.length <= 100000。

s 和 t 仅由小写英文字母组成。

输入： s = “cat”, t = “chat”。

输出： true。

解释：

将 s[1] 从 ‘a’ 替换为 ‘h’，得到字符串 “cht”。

“cht” 是 “chat” 的子序列，因为可以按顺序匹配 ‘c’、‘h’ 和 ‘t’。

题目来自力扣3983。

大体步骤如下：

• 状态一：表示完全没有使用过修改机会时，s 的前面已经有多少个字符成功按顺序匹配到了 t 的当前前缀中。
• 状态二：表示最多使用一次修改机会时，s 的前面已经有多少个字符成功按顺序匹配到了 t 的当前前缀中。这里“最多一次”可以是一次都没用，也可以是已经用掉了那唯一的一次修改。

一开始，两个状态都从 0 开始，表示还没有匹配任何字符。如果 s 的长度比 t 还长，那肯定不可能成为子序列，直接返回 false。

然后从左到右依次扫描 t 中的每一个字符。对于当前字符，会做几件事：

1. 先尝试让“已经用过修改机会”的状态继续正常匹配。
   也就是看 s 中当前待匹配的那个字符，是否正好等于 t 的当前字符。如果相等，就不需要额外修改，直接让这个状态往后走一位。

2. 再考虑在当前字符处使用修改机会。
   如果“完全没用过修改机会”的状态已经匹配了 s 的前若干个字符，那么我们可以把 s 中下一个还没匹配的字符改成当前 t 的字符，这样就能强行多匹配一个字符。于是“已经用过修改机会”的状态至少可以推进到“未用修改机会的状态 + 1”。如果原来这个状态已经更靠后，就保持不变。这一步体现了“最多改一个字符”的选择。

3. 然后更新“完全没用过修改机会”的状态。
   看 s 中当前待匹配的字符是否正好等于 t 的当前字符。如果相等，就正常匹配，这个状态也往后走一位。

4. 每次处理完当前字符后，检查“已经用过修改机会”的状态是否已经达到了 s 的总长度。
   如果达到了，说明整个 s 已经按顺序出现在 t 的处理过的部分里，而且最多只改了一个字符，因此可以直接返回 true。

如果 t 的所有字符都扫描完了，这个状态仍然没有达到 s 的总长度，说明无法做到，返回 false。

用例子 s = “cat”，t = “chat” 来看：

• 初始两个状态都是 0。
• 遇到 t 的 ‘c’：s 的第一个字符也是 ‘c’，所以两个状态都可以正常前进，都变成 1。
• 遇到 ‘h’：s 的第二个字符是 ‘a’，不等于 ‘h’。未用修改的状态不能前进，仍然是 1。但已用修改的状态可以借助修改机会，把 s 的第二个字符 ‘a’ 改成 ‘h’，于是这个状态推进到 2。
• 遇到 ‘a’：已用修改的状态当前待匹配的是 s 的第三个字符 ‘t’，不等于 ‘a’，不能正常前进；但它已经用过一次修改，不能再改，所以保持 2。未用修改的状态此时待匹配的是 s 的第二个字符 ‘a’，正好等于 ‘a’，所以前进到 2。
• 遇到 ‘t’：已用修改的状态待匹配的是 s 的第三个字符 ‘t’，正好等于 ‘t’，于是前进到 3。此时已达到 s 的总长度 3，返回 true。

整个过程中，只遍历了 t 一次，每个字符只做了常数次比较和更新操作，所以总的时间复杂度是 O(t 的长度)。额外使用的变量只有几个整数状态，不随字符串长度增长，所以总的额外空间复杂度是 O(1)。

Go完整代码如下：

packagemainimport("fmt")funccanMakeSubsequence(s,tstring)bool{n:=len(s)ifn>len(t){returnfalse}j0:=0// 在不修改的情况下，s 的前缀 [0, j0-1] 是 t 的当前前缀的子序列j1:=0// 在改过一次的情况下，s 的前缀 [0, j1-1] 是 t 的当前前缀的子序列for_,ch:=ranget{// j1 普通匹配ifs[j1]==byte(ch){j1++}// 也可以修改 s[j0] 为 ch，强行匹配j1=max(j1,j0+1)// j0 普通匹配ifs[j0]==byte(ch){j0++}ifj1==n{// s 是 t 的子序列returntrue}}returnfalse}funcmain(){s:="cat"t:="chat"result:=canMakeSubsequence(s,t)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defcanMakeSubsequence(s:str,t:str)->bool:n=len(s)ifn>len(t):returnFalseifn==0:returnTruej0=0# 不修改时，s 的前缀 [0, j0-1] 已匹配j1=0# 最多修改一次时，s 的前缀 [0, j1-1] 已匹配forchint:# j1 尝试正常匹配ifj1<nands[j1]==ch:j1+=1# 也可以把 s[j0] 修改为 ch，强行多匹配一个字符j1=max(j1,j0+1)# j0 尝试正常匹配ifj0<nands[j0]==ch:j0+=1ifj1==n:returnTruereturnFalseif__name__=="__main__":s="cat"t="chat"result=canMakeSubsequence(s,t)print(result)

C++完整代码如下：

#include<iostream>#include<string>#include<algorithm>boolcanMakeSubsequence(conststd::string&s,conststd::string&t){intn=static_cast<int>(s.size());if(n>static_cast<int>(t.size())){returnfalse;}if(n==0){returntrue;}intj0=0;// 不修改时，s 的前缀 [0, j0-1] 已匹配intj1=0;// 最多修改一次时，s 的前缀 [0, j1-1] 已匹配for(charch:t){// j1 尝试正常匹配if(j1<n&&s[j1]==ch){++j1;}// 也可以把 s[j0] 修改为 ch，强行多匹配一个字符if(j0<n){j1=std::max(j1,j0+1);}// j0 尝试正常匹配if(j0<n&&s[j0]==ch){++j0;}if(j1==n){returntrue;}}returnfalse;}intmain(){std::string s="cat";std::string t="chat";boolresult=canMakeSubsequence(s,t);std::cout<<std::boolalpha<<result<<std::endl;return0;}