题目重点:OA 第一题:每个连续三字符窗口首尾忽略大小写相同则计数;给出重叠窗口与 Unicode/ASCII 的边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练版字符串按 Unicode code point 遍历并用 casefold 比较;若在线测试只处理 ASCII,可改 lower,不把 Unicode 复杂边界当确定原题。
- 每个起点 i 的窗口 s[i:i+3] 单独计数,窗口可重叠;只比较第 1 与第 3 字符,中间任意。
- 长度<3 返回 0;空白/标点是否允许按输入契约处理。
解题路线
- 先从例子确认是窗口首尾比较,不要求三个字符整体回文去重;`axA` 的首尾忽略大小写相同。
- 从 i=0 扫到 n−3,若 normalize(s[i])==normalize(s[i+2]) 就答案+1;每次只推进 1,使重叠窗口保留。
- 若字符大小写折叠可能改变长度/等价关系,需与面试官约定字符规范;一般 ASCII 测试只需 toLowerCase。
- 用短串、全同字符、大小写交错、重叠匹配和帖中两个样例验证。
手动走一遍
`axA` 唯一窗口 `a x A`,计 1;`cxcbdb` 的六字符有四个三字符窗口,其中 `cxc` 和 `bdb` 计数,答案 2。`aaaa` 有两个重叠窗口,答案 2。
规模与取舍
n 个字符扫描 O(n) 时间、O(1) 附加空间(按单字符规范化常数成本);若先整体复制为规范化字符串则 O(n) 额外空间。
易错点与追问
容易失分的边界
- 每次跳 3 个字符,漏重叠窗口。
- 大小写比较只规范化首字符,尾字符保留原大小写。
- 把中间字符也要求等于首尾。
- 长度不足三时错误访问 s[i+2]。
继续深挖
- 若忽略重音符号怎样规范化?
- 流式字符块跨边界的三字符窗口如何计?
- 要求返回匹配起点而不只数量怎么改?
