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 中的每一个字符。对于当前字符会做几件事先尝试让“已经用过修改机会”的状态继续正常匹配。也就是看 s 中当前待匹配的那个字符是否正好等于 t 的当前字符。如果相等就不需要额外修改直接让这个状态往后走一位。再考虑在当前字符处使用修改机会。如果“完全没用过修改机会”的状态已经匹配了 s 的前若干个字符那么我们可以把 s 中下一个还没匹配的字符改成当前 t 的字符这样就能强行多匹配一个字符。于是“已经用过修改机会”的状态至少可以推进到“未用修改机会的状态 1”。如果原来这个状态已经更靠后就保持不变。这一步体现了“最多改一个字符”的选择。然后更新“完全没用过修改机会”的状态。看 s 中当前待匹配的字符是否正好等于 t 的当前字符。如果相等就正常匹配这个状态也往后走一位。每次处理完当前字符后检查“已经用过修改机会”的状态是否已经达到了 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)ifnlen(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强行匹配j1max(j1,j01)// j0 普通匹配ifs[j0]byte(ch){j0}ifj1n{// s 是 t 的子序列returntrue}}returnfalse}funcmain(){s:catt:chatresult:canMakeSubsequence(s,t)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defcanMakeSubsequence(s:str,t:str)-bool:nlen(s)ifnlen(t):returnFalseifn0:returnTruej00# 不修改时s 的前缀 [0, j0-1] 已匹配j10# 最多修改一次时s 的前缀 [0, j1-1] 已匹配forchint:# j1 尝试正常匹配ifj1nands[j1]ch:j11# 也可以把 s[j0] 修改为 ch强行多匹配一个字符j1max(j1,j01)# j0 尝试正常匹配ifj0nands[j0]ch:j01ifj1n:returnTruereturnFalseif__name____main__:scattchatresultcanMakeSubsequence(s,t)print(result)C完整代码如下#includeiostream#includestring#includealgorithmboolcanMakeSubsequence(conststd::strings,conststd::stringt){intnstatic_castint(s.size());if(nstatic_castint(t.size())){returnfalse;}if(n0){returntrue;}intj00;// 不修改时s 的前缀 [0, j0-1] 已匹配intj10;// 最多修改一次时s 的前缀 [0, j1-1] 已匹配for(charch:t){// j1 尝试正常匹配if(j1ns[j1]ch){j1;}// 也可以把 s[j0] 修改为 ch强行多匹配一个字符if(j0n){j1std::max(j1,j01);}// j0 尝试正常匹配if(j0ns[j0]ch){j0;}if(j1n){returntrue;}}returnfalse;}intmain(){std::string scat;std::string tchat;boolresultcanMakeSubsequence(s,t);std::coutstd::boolalpharesultstd::endl;return0;}
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 中的每一个字符。对于当前字符会做几件事先尝试让“已经用过修改机会”的状态继续正常匹配。也就是看 s 中当前待匹配的那个字符是否正好等于 t 的当前字符。如果相等就不需要额外修改直接让这个状态往后走一位。再考虑在当前字符处使用修改机会。如果“完全没用过修改机会”的状态已经匹配了 s 的前若干个字符那么我们可以把 s 中下一个还没匹配的字符改成当前 t 的字符这样就能强行多匹配一个字符。于是“已经用过修改机会”的状态至少可以推进到“未用修改机会的状态 1”。如果原来这个状态已经更靠后就保持不变。这一步体现了“最多改一个字符”的选择。然后更新“完全没用过修改机会”的状态。看 s 中当前待匹配的字符是否正好等于 t 的当前字符。如果相等就正常匹配这个状态也往后走一位。每次处理完当前字符后检查“已经用过修改机会”的状态是否已经达到了 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)ifnlen(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强行匹配j1max(j1,j01)// j0 普通匹配ifs[j0]byte(ch){j0}ifj1n{// s 是 t 的子序列returntrue}}returnfalse}funcmain(){s:catt:chatresult:canMakeSubsequence(s,t)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defcanMakeSubsequence(s:str,t:str)-bool:nlen(s)ifnlen(t):returnFalseifn0:returnTruej00# 不修改时s 的前缀 [0, j0-1] 已匹配j10# 最多修改一次时s 的前缀 [0, j1-1] 已匹配forchint:# j1 尝试正常匹配ifj1nands[j1]ch:j11# 也可以把 s[j0] 修改为 ch强行多匹配一个字符j1max(j1,j01)# j0 尝试正常匹配ifj0nands[j0]ch:j01ifj1n:returnTruereturnFalseif__name____main__:scattchatresultcanMakeSubsequence(s,t)print(result)C完整代码如下#includeiostream#includestring#includealgorithmboolcanMakeSubsequence(conststd::strings,conststd::stringt){intnstatic_castint(s.size());if(nstatic_castint(t.size())){returnfalse;}if(n0){returntrue;}intj00;// 不修改时s 的前缀 [0, j0-1] 已匹配intj10;// 最多修改一次时s 的前缀 [0, j1-1] 已匹配for(charch:t){// j1 尝试正常匹配if(j1ns[j1]ch){j1;}// 也可以把 s[j0] 修改为 ch强行多匹配一个字符if(j0n){j1std::max(j1,j01);}// j0 尝试正常匹配if(j0ns[j0]ch){j0;}if(j1n){returntrue;}}returnfalse;}intmain(){std::string scat;std::string tchat;boolresultcanMakeSubsequence(s,t);std::coutstd::boolalpharesultstd::endl;return0;}
