数据结构与算法 / 系统课时

字符串双指针

字符串双指针

字符串双指针适合处理“两端向中间收缩”的问题。本课以忽略非字母数字字符和大小写的回文判断为主例,展示如何维护边界、跳过无效字符并保证每轮都有进展。

学习目标

  • 识别左右指针适用的字符串问题
  • 在移动指针时正确处理过滤和边界
  • 使用 Unicode 代码点完成稳健的回文判断

左右指针的循环不变量

将字符串转换为代码点数组后,令 left = 0、right = n - 1。循环过程中,left 左侧和 right 右侧的有效字符已经验证完毕,尚未判断的范围始终是 [left, right]。

每轮先让左指针跳过无效字符,再让右指针跳过无效字符。若两侧仍未交叉,就统一大小写并比较;相等时同时收缩,不相等时立即返回 false。

字符串回文双指针流程

完整示例

下面的 Java 17 程序使用 codePoints(),避免把补充字符拆成两个独立 char。该实现适合一般文本判断,但不处理语言相关的复杂大小写折叠与字素簇规范化。

java
public class StringTwoPointerDemo {

    public static void main(String[] args) {
        String[] samples = {
            "A man, a plan, a canal: Panama",
            "算法,法算",
            "OpenAI"
        };

        for (String sample : samples) {
            System.out.println(sample + " -> " + isPalindrome(sample));
        }
    }

    private static boolean isPalindrome(String text) {
        int[] codePoints = text.codePoints().toArray();
        int left = 0;
        int right = codePoints.length - 1;

        while (left < right) {
            // 两侧先各自跳过非字母数字字符
            while (left < right
                && !Character.isLetterOrDigit(codePoints[left])) {
                left++;
            }
            while (left < right
                && !Character.isLetterOrDigit(codePoints[right])) {
                right--;
            }

            int leftValue = Character.toLowerCase(codePoints[left]);
            int rightValue = Character.toLowerCase(codePoints[right]);
            if (leftValue != rightValue) {
                return false;
            }

            // 比较成功后必须同时收缩,保证循环继续推进
            left++;
            right--;
        }
        return true;
    }
}

预期输出:

text
A man, a plan, a canal: Panama -> true
算法,法算 -> true
OpenAI -> false

空字符串、只包含标点的字符串以及单个有效字符都会返回 true,因为不存在不对称字符对。

正确性与复杂度

每个代码点最多被左右指针访问常数次,判断阶段时间复杂度为 O(n)。由于示例先创建代码点数组,额外空间复杂度为 O(n)。只处理基本 char 范围时,可以直接在原字符串上移动下标,将额外空间降为 O(1)。

算法正确性的核心是循环不变量:已越过的两端内容已经完成验证;每次有效比较后同时收缩;任何不匹配都能立即否定回文性质。

常见错误

跳过无效字符时若不检查 left < right,全标点输入可能越界。比较成功后只移动一侧,会让另一侧字符被重复使用,甚至形成死循环。连续调用 replaceAll、toLowerCase 和反转虽然容易书写,却会创建多个中间对象,也掩盖双指针的边界逻辑。

练习

实现“删除最多一个字符后是否能成为回文”。首次出现不匹配时,分别尝试跳过左字符和跳过右字符,两个分支任一成立即可;输入 abca 应返回 true。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

字符串双指针

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通