题目描述
思路解析动画文字版
记牢这句话:固定一对起点、沿对角线一起扩、边扩边数不同字符,只要不同字符恰好是 1 个就记一对,数到第 2 个不同就收手。下面每一帧都在套这个思路,起点对一个一个换。
起点对 (0, 0) · 出发：换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (0, 0) · 扩到长度 1：指针走到 s[0] = "c" 和 t[0] = "c",两个字符相同,窗口里的不同个数不变,还是 0。 现在 s 的窗口是 "c",t 的窗口是 "c"。一个不同都没有,两段完全一样,不符合「恰好 1 个不同」,不记。
起点对 (0, 0) · 扩到长度 2：指针走到 s[1] = "a" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "ca",t 的窗口是 "cb"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 1。
起点对 (0, 0) · 扩到长度 3：指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 1。 现在 s 的窗口是 "cat",t 的窗口是 "cbt"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 2。
起点对 (0, 1) · 出发：换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (0, 1) · 扩到长度 1：指针走到 s[0] = "c" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "c",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 3。
起点对 (0, 1) · 扩到长度 2：指针走到 s[1] = "a" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 2。 现在 s 的窗口是 "ca",t 的窗口是 "bt"。不同已经攒到 2 个了,再往右扩只会更多,不可能回到 1 个,这一对到此为止,指针收手换下一对起点。
起点对 (0, 2) · 出发：换一对新起点。让 s 的指针停在下标 0 的 "c",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (0, 2) · 扩到长度 1：指针走到 s[0] = "c" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "c",t 的窗口是 "t"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 4。
起点对 (1, 0) · 出发：换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (1, 0) · 扩到长度 1：指针走到 s[1] = "a" 和 t[0] = "c",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "c"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 5。
起点对 (1, 0) · 扩到长度 2：指针走到 s[2] = "t" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 2。 现在 s 的窗口是 "at",t 的窗口是 "cb"。不同已经攒到 2 个了,再往右扩只会更多,不可能回到 1 个,这一对到此为止,指针收手换下一对起点。
起点对 (1, 1) · 出发：换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (1, 1) · 扩到长度 1：指针走到 s[1] = "a" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 6。
起点对 (1, 1) · 扩到长度 2：指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 1。 现在 s 的窗口是 "at",t 的窗口是 "bt"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 7。
起点对 (1, 2) · 出发：换一对新起点。让 s 的指针停在下标 1 的 "a",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (1, 2) · 扩到长度 1：指针走到 s[1] = "a" 和 t[2] = "t",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "a",t 的窗口是 "t"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 8。
起点对 (2, 0) · 出发：换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 0 的 "c"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (2, 0) · 扩到长度 1：指针走到 s[2] = "t" 和 t[0] = "c",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "t",t 的窗口是 "c"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 9。
起点对 (2, 1) · 出发：换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 1 的 "b"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (2, 1) · 扩到长度 1：指针走到 s[2] = "t" 和 t[1] = "b",两个字符不同,窗口里的不同个数加一,变成 1。 现在 s 的窗口是 "t",t 的窗口是 "b"。不同的字符恰好 1 个,这正是题目要的,把这一对记下来,答案变成 10。
起点对 (2, 2) · 出发：换一对新起点。让 s 的指针停在下标 2 的 "t",t 的指针停在下标 2 的 "t"。接下来这两个指针会手拉手沿对角线一起往右走,每走一格就把对上的两个字符比一比,数窗口里有几个不同。现在窗口里还一个字符都没比,先看好起跑线。
起点对 (2, 2) · 扩到长度 1：指针走到 s[2] = "t" 和 t[2] = "t",两个字符相同,窗口里的不同个数不变,还是 0。 现在 s 的窗口是 "t",t 的窗口是 "t"。一个不同都没有,两段完全一样,不符合「恰好 1 个不同」,不记。
完成 · 答案 10：九对起点都沿对角线扫过了。回放一下:贡献最多的是起点对 (0, 0) 和 (1, 1),它们各扩出了 2 对;其余起点对有的记一对、有的因为完全相同或太快撞上第 2 个不同而记不到。把每对起点记下的对数全加起来,正好是 10。全程只做了对齐、比较、计数三种常数操作。
边界先想清:各 1 个字符且不同就是 1 对;两串字符全一样时所有窗口都是 0 个不同、答案为 0;短串里也要把短窗口、长窗口分别数。
面试重点:合法窗口的那个不同字符唯一,所以可按中心枚举、左右数相等相乘;更快有 O(m·n) 的前后缀 DP;这类「子串恰好 k 处不同」常用固定锚点扩或滑窗维护不同计数。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def countSubstrings(self, s: str, t: str) -> int: ans = 0 m, n = len(s), len(t) for i, a in enumerate(s): for j, b in enumerate(t): if a != b: l = r = 0 while i > l and j > l and s[i - l - 1] == t[j - l - 1]: l += 1 while ( i + r + 1 < m and j + r + 1 < n and s[i + r + 1] == t[j + r + 1] ): r += 1 ans += (l + 1) * (r + 1) return ans复杂度
- 时间：O(m·n·min(m, n))，m、n 是两个字符串长度。动画里起点对有 m·n 个,每对沿对角线最多扩 min(m, n) 格;参考代码枚举 m·n 个中心、每个向两边扩也是 min(m, n) 量级。两种数法都是这个上界,最坏同阶
- 空间：O(1)，从头到尾只用了几个下标和计数器(起点 i、j,偏移 k,不同个数 mis,或参考代码的 l、r、ans),不随字符串变长而增加,峰值是常数
易错点
面试追问把动画讲成自己的话
追问参考代码为什么能不枚举所有起点,只枚举「那个不同的字符」当中心?
追问这道题还有没有更快的解法?
追问遇到「子串恰好有 k 处不同」这一类题,通用套路是什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使字符串平衡的最少删除次数
LeetCode 1653 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题