学习目标
- 从字符串或双端队列的首尾取字符比较，直到中间相遇。
- 区分奇数与偶数长度，并明确大小写、数字和标点处理范围。
- 证明最多检查一半的字符对。
前置知识与环境
建议先学习第 2 章栈与队列。使用 ISO C++17；开始前可在本目录运行 make doctor。
任务
判断字符串从左到右与从右到左是否逐字符相同。按输入字符原样比较，不进行大小写转换、删空格或忽略数字；例如 abba 是回文，abca 不是。
输入格式
一行仅含小写英文字母 a-z 与数字 0-9 的非空字符串，长度 1..200000，不含空格或标点。
输出格式
回文输出 YES，否则输出 NO。
数据范围与限制
- 输入规模不超过
200000，除题面另有说明外整数使用 64 位有符号范围。 - 标准输出只保留题目要求的结果；调试信息写入标准错误。
- 目标算法应为线性或摊还线性时间，辅助空间不超过
O(n)。
边界与验收重点
- 单字符、偶数长度、奇数长度和靠近中心的第一处不等。
- 字符
'1'与字母'l'不同；题目不做规范化。 - 用两端下标或双端队列均能体现本题对称访问的逻辑。
如何验证
powershell
make doctor
make run
make score未安装 Make 时，在仓库根目录运行：
powershell
pnpm lab:validate -- labs/chapter-02/exercise/E-02-17-palindrome-deque
pnpm lab:run -- labs/chapter-02/exercise/E-02-17-palindrome-deque
pnpm lab:score -- labs/chapter-02/exercise/E-02-17-palindrome-deque思考与复盘
- 奇数长度的正中字符需要与谁比较？
- 两端下标为何可以在不复制字符串的情况下完成判断？
思考题参考
- 不需要与其他字符比较；所有两侧字符对一致即可。
- 每次访问两个位置后向中间移动，原字符串保持不变。
题解
点击查看题解
思路与不变量
用左右两个下标分别指向尚未比较的首尾字符。每一步比较这两个字符，再同时向中间移动；因此已检查的两侧字符对都相等，未检查部分仍是一个连续区间。
算法步骤
- 初始化
left=0、right=|s|； - 当
left < right时先令right指向最后一个未检查位置，再比较s[left]与s[right]； - 发现不同立即输出
NO，否则继续收缩区间； - 所有字符对都相等时输出
YES。
正确性说明
回文的定义要求每个位置都等于其对称位置。算法按外层到内层检查全部字符对，任一不等立即判定非回文；若全部通过，奇数长度的中心字符无需配对，所有必要条件都满足。
复杂度分析
- 时间复杂度：
O(|s|)，最多比较一半字符对； - 额外空间：
O(1)，只使用两个下标。
边界注意
- 单字符和空心的中心字符都天然满足回文条件；
- 字符按原样比较，不转换大小写，也不忽略数字；
- 输入不含空格，因此使用
operator>>读取不会丢失题面字符。