0125. Valid Palindrome ====================== 题目信息 -------- :题号: 0125. 验证回文串 :难度: Easy :主题: 字符串、双指针、字符归一化 :原题: `LeetCode 0125 `_ :重点: 分清逻辑序列与物理存储,按需寻找下一对有效字符,以双指针消除完整清洗副本 题目重述 -------- 给定字符串 ``s``,只保留英文字母和十进制数字,并把英文字母视为不区分大小写。判断保留下来的字符序列 是否为回文,即从左向右读取与从右向左读取完全相同。 原串只含可打印 ASCII 字符,长度在 ``[1, 2 * 10^5]`` 内。若删除无效字符后序列为空,也应返回 ``true``。 自建示例 -------- * ``s = "A man, a plan, a canal: Panama"``:有效字符依次组成 ``amanaplanacanalpanama``,返回 ``true``; * ``s = "0P"``:数字 ``0`` 与字母 ``p`` 不相等,返回 ``false``; * ``s = ".,!"``:没有有效字符,清洗结果为空序列,返回 ``true``; * ``s = "a-b_Ca"``:两端 ``a/a`` 相等,随后比较 ``b/c``,返回 ``false``。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: bool isAsciiLetterOrDigit(char ch) { return ('0' <= ch && ch <= '9') || ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z'); } char normalized(char ch) { if ('A' <= ch && ch <= 'Z') { return static_cast(ch - 'A' + 'a'); } return ch; } bool buildNormalizedString(const std::string& s) { std::string cleaned; cleaned.reserve(s.size()); for (char ch : s) { if (isAsciiLetterOrDigit(ch)) { cleaned.push_back(normalized(ch)); } } int left = 0; int right = static_cast(cleaned.size()) - 1; while (left < right) { if (cleaned[left] != cleaned[right]) { return false; } ++left; --right; } return true; } bool compareInOriginalString(const std::string& s) { int left = 0; int right = static_cast(s.size()) - 1; while (left < right) { while (left < right && !isAsciiLetterOrDigit(s[left])) { ++left; } while (left < right && !isAsciiLetterOrDigit(s[right])) { --right; } if (normalized(s[left]) != normalized(s[right])) { return false; } ++left; --right; } return true; } public: bool isPalindrome(std::string s) { return compareInOriginalString(s); } }; 题解 ---- 先明确真正比较的对象 ~~~~~~~~~~~~~~~~~~~~ 回文定义作用在“清洗后的字符序列”上,而不是原字符串的物理相邻位置。标点和空格不参与序列;大写字母 也不是另一个字符,而是要先映射到对应小写字母再比较。若直接拿 ``s[left]`` 与 ``s[right]`` 比较, ``"a,a"`` 会在第一步比较 ``a`` 和 ``a`` 后碰到逗号;若只跳过空格,其他标点仍会制造错误。算法必须同时 表达两件事:找到逻辑序列的下一项,以及比较归一化后的值。 方案一:显式构造逻辑序列 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 最直观的方法是扫描原串,把每个有效字符归一化后放入 ``cleaned``,再检查 ``cleaned`` 的首尾镜像位置。 这正好对应题目定义,因此正确性直接:``cleaned`` 就是题目要求比较的序列,全部镜像位置相等当且仅当它是 回文。 ``buildNormalizedString`` 保留这一基线。它把“过滤和归一化”与“回文检查”分成两个清晰阶段,便于理解和 调试;代价是即使首尾第一对字符就不相等,也已经扫描并复制了整个字符串,最坏还要保存 ``O(n)`` 个字符。 结构信息:回文检查只按镜像位置取值 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 判断回文并不需要随机访问完整的 ``cleaned``,任一时刻只需要它最左和最右尚未比较的字符。原串中从左侧 遇到的下一个有效字符,恰好就是逻辑序列的下一项;从右侧遇到的下一个有效字符,恰好就是逻辑序列的最后 一项。因此可以让两个指针直接在原串上移动,遇到无效字符就各自跳过,找到一对有效字符后再归一化比较。 这不是改变了清洗规则,而是把“先生成全部清洗结果”压缩为“需要哪一对就生成哪一对”。每个已经跨过的 字符再也不会参与后续比较,所以无需保存它。 双指针的不变量与删除规则 ~~~~~~~~~~~~~~~~~~~~~~~~ 每轮外层循环开始时,``left`` 左侧和 ``right`` 右侧的逻辑字符已经成对验证相等。两段内层循环分别寻找 剩余逻辑序列的首字符和尾字符:无效字符不会出现在清洗结果中,跳过它等价于从未存储它,不会漏掉候选。 找到两端后: * 归一化值不同,当前就是清洗序列的一对镜像位置,回文条件已经被否定,可以立即返回; * 归一化值相同,这一对已经完成验证,同时向内移动后,不变量对下一轮继续成立; * 指针相遇或交错时,剩余逻辑序列至多有一个字符,不再存在未验证的镜像对,因此返回 ``true``。 最后一条也覆盖清洗结果为空的情况。内层循环使用 ``left < right`` 作为边界,所以即使原串全是标点,也 不会越过数组边界;两指针最终相遇,单个位置无需与自身之外的字符比较。 具体走读 ~~~~~~~~ 以 ``s = "a-b_Ca"`` 为例: .. list-table:: :header-rows: 1 * - 待处理区间 - 跳过字符 - 实际比较 - 结论 * - ``[0, 5]`` - 无 - ``a`` 与 ``a`` - 相等,删除这一对 * - ``[1, 4]`` - 左侧 ``-`` - ``b`` 与 ``C``,归一化为 ``b`` 与 ``c`` - 不等,立即返回 ``false`` 这里的下划线尚未访问,因为更外层的有效字符已经证明结果为假。显式清洗方案仍会处理它,原串双指针则 自然省掉了与结论无关的后续工作。 代码对应与主解选择 ~~~~~~~~~~~~~~~~~~ ``isAsciiLetterOrDigit`` 明确实现题目的 ASCII 字符域,避免区域设置影响字符分类;``normalized`` 只转换 大写英文字母,数字和小写字母保持不变。``compareInOriginalString`` 中两次跳过必须相互独立,因为左右两端 可能有不同数量、不同种类的无效字符;先跳完两侧再比较,才得到清洗序列中真正对应的一对。 公开入口采用原串双指针:它与显式清洗具有相同的线性扫描上界,却把工作空间从 ``O(n)`` 降到 ``O(1)``, 并能在发现首个不匹配时提前结束。显式构造法保留为方案演进的起点,它的收益是概念分层更直接,适合验证 规则;没有必要再保留递归版本,因为它不删除搜索工作,只把指针状态转移到调用栈并增加 ``O(n)`` 栈空间。 复杂度分析 ~~~~~~~~~~ 两种方法的时间复杂度都是 ``O(n)``。显式构造法需要 ``O(n)`` 工作空间;主解中每个指针只朝中心移动, 每个原字符最多被检查常数次,工作空间为 ``O(1)``。