2026-10-08：一次替换后的子序列。用go语言，给定两个只包含小写字母的字符串 s 和 t。你可以在 s 中至多改动一个位置上的字符，把它换成

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完整代码如下：

package main

 import (
    "fmt"
)

 func canMakeSubsequence(s, t string)bool {
    n := len(s)
    if n > len(t) {
        returnfalse
    }

     j0 := 0// 在不修改的情况下，s 的前缀 [0, j0-1] 是 t 的当前前缀的子序列
    j1 := 0// 在改过一次的情况下，s 的前缀 [0, j1-1] 是 t 的当前前缀的子序列
    for _, ch := range t {
        // j1 普通匹配
        if s[j1] == byte(ch) {
            j1++
        }

         // 也可以修改 s[j0] 为 ch，强行匹配
        j1 = max(j1, j0+1)

         // j0 普通匹配
        if s[j0] == byte(ch) {
            j0++
        }

         if j1 == n {
            // s 是 t 的子序列
            returntrue
        }
    }
    returnfalse
}

 func main() {
    s := "cat"
    t := "chat"
    result := canMakeSubsequence(s, t)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def canMakeSubsequence(s: str, t: str) -> bool:
    n = len(s)
    if n > len(t):
        return False

     if n == 0:
        return True

     j0 = 0  # 不修改时，s 的前缀 [0, j0-1] 已匹配
    j1 = 0  # 最多修改一次时，s 的前缀 [0, j1-1] 已匹配

     for ch in t:
        # j1 尝试正常匹配
        if j1 < n and s[j1] == ch:
            j1 += 1

         # 也可以把 s[j0] 修改为 ch，强行多匹配一个字符
        j1 = max(j1, j0 + 1)

         # j0 尝试正常匹配
        if j0 < n and s[j0] == ch:
            j0 += 1

         if j1 == n:
            return True

     return False

 if __name__ == "__main__":
    s = "cat"
    t = "chat"
    result = canMakeSubsequence(s, t)
    print(result)

C++完整代码如下：

  

  


 bool canMakeSubsequence(const std::string& s, const std::string& t) {
    int n = static_cast(s.size());
    if (n > static_cast(t.size())) {
        returnfalse;
    }
    if (n == 0) {
        returntrue;
    }

     int j0 = 0; // 不修改时，s 的前缀 [0, j0-1] 已匹配
    int j1 = 0; // 最多修改一次时，s 的前缀 [0, j1-1] 已匹配

     for (char ch : 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;
}

 int main() {
    std::string s = "cat";
    std::string t = "chat";
    bool result = canMakeSubsequence(s, t);
    std::cout << std::boolalpha << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。