数据结构与算法 / 系统课时
字符串双指针
字符串双指针
字符串双指针适合处理“两端向中间收缩”的问题。本课以忽略非字母数字字符和大小写的回文判断为主例,展示如何维护边界、跳过无效字符并保证每轮都有进展。
学习目标
- 识别左右指针适用的字符串问题
- 在移动指针时正确处理过滤和边界
- 使用 Unicode 代码点完成稳健的回文判断
左右指针的循环不变量
将字符串转换为代码点数组后,令 left = 0、right = n - 1。循环过程中,left 左侧和 right 右侧的有效字符已经验证完毕,尚未判断的范围始终是 [left, right]。
每轮先让左指针跳过无效字符,再让右指针跳过无效字符。若两侧仍未交叉,就统一大小写并比较;相等时同时收缩,不相等时立即返回 false。

完整示例
下面的 Java 17 程序使用 codePoints(),避免把补充字符拆成两个独立 char。该实现适合一般文本判断,但不处理语言相关的复杂大小写折叠与字素簇规范化。
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;
}
}预期输出:
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。