专题进阶 · 基础与数据结构推荐总顺序 · 第 25 / 148 课

分清字符、码点、字节和可见字符,避免切片与拼接的隐藏成本。

先学会这些,再进入本课 数组
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 基础与数据结构

字符串String

把字符或码点序列视作数组,但要注意不可变字符串的复制与 Unicode 编码成本。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

分清字符、码点、字节和可见字符,避免切片与拼接的隐藏成本。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

反转字符串、统计长度和查找字符看起来像数组操作,为什么同一段文字在不同语言中长度会不同?

02一步步得到方法

先决定你要操作哪种单位

字节是编码后的存储单位;Unicode 码点是字符编号;用户眼里一个可见字符还可能由多个码点组成,例如 e 与组合重音。Python str 通常按码点索引,UTF-8 字节串按字节索引,二者不能混为一谈。

本课的算法明确按码点工作。若要处理人类可见字符,应先按字素簇分段;按码点倒序可能拆开组合字符或 Emoji 序列。输入约定是算法正确性的一部分。

不可变字符串隐藏了什么工作

Python 字符串不能像列表一样原地赋值。a+b 要形成新字符串,切片也通常创建新对象。循环 s=s+piece 可能反复复制已经积累的前缀,最坏总工作量 1+2+…+n。

把片段先放入列表,最后 join 一次,可以先知道结果长度并按总字符数组合。这个方法减少重复复制,但列表和最终字符串仍需要空间,不能称为原地算法。

从双指针到规范化

判断回文时,不必先构造完整反转副本;可以比较两端码点并向内缩。若问题要求忽略大小写、空格或等价 Unicode 表示,应先明确规范化规则,再比较,不能默默删除信息。

03把一个小例子完全算清楚

按 Python 码点处理 s='A你🙂';另观察 'e\u0301'。

步骤计算与状态为什么这样做
编码前len('A你🙂')=3三个 Unicode 码点
UTF-8 编码字节数 1+3+4=8一个码点不一定对应一个字节
组合重音len('e\u0301')=2视觉上常显示一个带重音字母
反转码点'🙂你A'本例各可见字符恰好都是单一码点

窄屏可左右滑动表格,阅读完整计算与理由。

长度取决于计数单位。本课代码适用于按码点定义的回文与拼接任务。

04为什么这个方法成立

  1. 双指针外部已经验证的对称位置相等。
  2. 若当前两个码点不同,整个字符串不可能为回文;相同时缩小到内部区间。
  3. 指针相遇后所有对称位置都已检查,空串和单码点串自然成立。

05把推导翻译成代码

Python · 可独立运行的教学实现

def palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def concatenate(parts):
    return "".join(parts)

逐个理解关键决定

s[left] != s[right]
这里比较码点;不是比较 UTF-8 字节,也没有自动忽略大小写。
"".join(parts)
先收集片段,再组合输出;结果长度是所有片段码点数之和。

06时间、空间与实现范围

长度 n 的回文检查最坏比较 floor(n/2) 对,时间 O(n),除输入外辅助空间 O(1)。

join 时间与总输出长度 L 及片段数相关,输出空间 O(L)。规范化、分段等预处理需要另算。

07改变条件,检查哪里会出错

把 UTF-8 字节倒序后解码

可能破坏多字节编码。先解码为文本,再按任务规定的码点或字素簇处理。

认为视觉上相同就一定逐码点相同

例如预组合 é 与 e+组合重音可有不同表示;需要时先采用一致的 Unicode 规范化。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

'上海自来水来自海上' 是码点回文吗?

需要一点提示

依次比较首尾。

查看解析与答案

是。每一对对称汉字相等。

练习 2 · 边界与辨析

'Aa' 在本课实现中返回什么?

需要一点提示

代码没有改写大小写。

查看解析与答案

False。若题意忽略大小写,需要显式 casefold 等规则,并重新界定预处理成本。

练习 3 · 变式与迁移

把 1000 个长度 1 的片段累加拼接,为什么可能比 join 慢?

需要一点提示

累计被复制的旧前缀。

查看解析与答案

普通模型中复制量可达 1+2+…+1000;join 以总长度为基准组装。不要把某个解释器的特定优化当成通用保证。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Python 官方教程 · 数据结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。