Lesson9 字符串双指针算法专题

目录

1. 双指针概述
   • 对撞指针解题步骤
   • 对撞指针伪代码模版
   • 对撞指针适用范围
2. 例题讲解
   • LC 344 反转字符串
   • LC 125 验证回文串
3. 举一反三
   • LC 345 反转字符串中的元音字母
   • LC 917 仅仅反转字母
   • LC 680 验证回文串 II
4. 课后练习

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」；本章仅针对字符串对撞指针进行介绍和题目分析。

1 对撞指针

对撞指针：指的是两个指针left、right分别指向序列第一个元素和最后一个元素，然后left指针不断递增，right不断递减，直到两个指针的值相撞（即 left== right），或者满足其他要求的特殊条件为止。

1.1 对撞指针解题步骤

1. 使用两个指针left，right。left指向序列第一个元素，即：left=0，right指向序列最后一个元素，即：right=len(nums)-1。
2. 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移，left+=1。当满足另外一定条件时，将右指针左移，right-=1。
3. 直到两指针相撞（即 left==right），或者满足其他要求的特殊条件时，跳出循环体。

1.2 对撞指针伪代码模版

left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

return 没找到 或 找到对应值

1.3 对撞指针适用范围

对撞指针一般用来解决有序数组或者字符串问题：

• 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
• 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

2 例题讲解

2.1 LC 344 反转字符串

问题描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组。

思路分析

对于长度为 N 的待被反转的字符数组，我们可以观察反转前后下标的变化。反转前字符数组为 s[0] s[1] s[2] ... s[N - 1]，反转后为 s[N - 1] s[N - 2] ... s[0]。因此可以使用双指针的方式，左指针从开始位置，右指针从结束位置开始，逐步交换字符。

参考解答 1 双指针解法

class Solution {
    public void reverseString(char[] s) {
        int left = 0;  // 左指针
        int right = s.length - 1;  // 右指针

        while (left < right) {
            // 交换左右指针的字符
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            // 移动指针
            left++;
            right--;
        }
    }
}

代码说明

1. 初始化指针：

   • left 指针指向字符数组的首元素，right 指针指向最后一个元素。

2. 交换字符：

   • 在 while 循环中，当 left 小于 right 时，交换 s[left] 和 s[right] 的字符。

3. 指针移动：

   • 交换后，left 指针向右移动（left++），right 指针向左移动（right--）。

4. 结束条件：

   • 当 left 大于或等于 right 时，反转结束，直接返回。

在 Java 中，标准的 String 类没有提供 reverse() 方法来直接反转字符串，但你可以使用 StringBuilder 类的 reverse() 方法来实现这一功能。StringBuilder 是一个可变的字符序列，适合用于字符串的修改和操作。

参考解答 2 使用 StringBuilder 的 reverse() 方法

class Solution {
    public void reverseString(char[] s) {
        // 将字符数组转换为 StringBuilder
        StringBuilder sb = new StringBuilder();
        sb.append(s);

        // 反转 StringBuilder 中的内容
        sb.reverse();

        // 将反转后的内容复制回字符数组
        for (int i = 0; i < s.length; i++) {
            s[i] = sb.charAt(i);
        }
    }
}

注意事项

• 使用 StringBuilder 的 reverse() 方法虽然简洁，但它并不是原地修改字符数组，而是创建了一个新的 StringBuilder 对象。因此，它并不是原地算法。
• 如果需要原地反转字符数组，请使用前面提到的双指针法，而不是 StringBuilder。

2.2 LC 125 验证回文串

问题描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

提示

• 需要忽略字符串中的空格、标点符号等非字母数字字符，并且在判断回文时不区分大小写。
• 可以使用双指针从两端向中间移动，逐字符检查是否相等。

思路分析

初始化双指针

• left 指针：指向字符串的开始（s[0]）。
• right 指针：指向字符串的结束（s[length - 1]）。

循环判断

我们会用一个 while 循环来遍历字符串，条件是 left < right，表示我们仍然没有碰到字符串的中间。

字符过滤

在每次循环中，我们需要保证 left 和 right 指向的都是有效的字母或数字字符：

• 左指针：如果 s[left] 不是字母或数字，就将 left 右移（left++），直到找到一个有效字符或越过 right。

• 右指针：如果 s[right] 不是字母或数字，同样将 right 左移（right--），直到找到一个有效字符或越过 left。

这个过程确保了我们只关注字母和数字，忽略其他所有字符。

字符比较

一旦两个指针分别指向有效的字符，我们就可以进行比较：

• 将 s[left] 和 s[right] 转换为小写进行比较（使用 Character.toLowerCase() 方法）。如果这两个字符不相等，那么可以立即返回 false，因为这说明字符串不是回文的。

移动指针

如果比较成功（即 s[left] 和 s[right] 相等），我们就可以继续将 left 右移，right 左移，继续向中间检查。

完成循环

当 left 不再小于 right 时，说明已经检查了整个字符串。如果没有发现不匹配的字符，说明字符串是一个回文串，可以返回 true。

参考解答

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // 找到左侧的字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // 找到右侧的字母数字字符
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            // 比较字符，忽略大小写
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;     
    }
}

3 举一反三

3.1 LC 345 反转字符串中的元音字母

问题描述

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

提示

• 你需要在原地反转字符串中的元音字母，同时保持其他字符的位置不变。
• 注意处理大小写不敏感的元音字符。

思路分析

初始化指针：

• 创建两个指针，l 和 r。l 指向字符串的起始位置，r 指向字符串的末尾。

• 定义元音字母集合：

• 使用一个集合 vowels 存储所有的元音字母（包括大小写）。这样可以方便地检查字符是否为元音。

遍历字符串：

• 使用一个 while 循环来遍历字符数组，当 l < r 时继续循环。
• 在循环内部，首先移动左指针 l，直到找到一个元音字母。
• 然后移动右指针 r，直到找到一个元音字母。

交换元音字母：

• 一旦两个指针都指向元音字母，进行交换。如果此时 l 仍然小于 r，则继续向内移动指针。

结束循环：

• 如果 l 不再小于 r，说明已经遍历完所有的元音字母，退出循环。

返回结果：

• 最后，将字符数组转换回字符串并返回。

参考解答

class Solution {
    public String reverseVowels(String s) {
        char[] chars = s.toCharArray(); // 将字符串转换为字符数组
        int l = 0; // 左指针
        int r = chars.length - 1; // 右指针
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')); // 存储元音字母

        while (l < r) {
            // 移动左指针直到找到元音字母
            while (l < r && !vowels.contains(chars[l])) {
                l++;
            }
            // 移动右指针直到找到元音字母
            while (l < r && !vowels.contains(chars[r])) {
                r--;
            }
            // 交换元音字母
            if (l < r) {
                char temp = chars[l];
                chars[l] = chars[r];
                chars[r] = temp;
                l++;
                r--;
            }
        }

        return new String(chars); // 将字符数组转换回字符串
    }
}

3.2 LC 917 仅仅反转字母

问题描述

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

提示

• 只需要反转字母，其他字符保持不变。
• 可以使用双指针法来遍历和交换字母。

思路分析

初始化指针：

• 创建两个指针，l 和 r。l 指向字符串的起始位置，r 指向字符串的末尾。

双指针遍历：

• 使用 while 循环遍历字符数组，条件是 l < r。
• 在循环内部：
• 首先，移动左指针 l，直到找到一个字母。使用 Character.isLetter(chars[l]) 来检查当前字符是否为字母。
• 然后，移动右指针 r，直到找到一个字母，使用同样的方法进行检查。

交换字母：

• 当 l 和 r 都指向字母时，交换它们的值。
• 之后，l 指针向右移动，r 指针向左移动，以便继续查找下一个字母。

结束循环：

• 当 l 不再小于 r 时，意味着已经完成所有的字母交换，退出循环。

返回结果：

• 最后，将字符数组转换回字符串并返回。

参考解答

class Solution {
    public String reverseOnlyLetters(String s) {
        char[] chars = s.toCharArray(); // 将字符串转换为字符数组
        int l = 0; // 左指针
        int r = chars.length - 1; // 右指针

        while (l < r) {
            // 移动左指针直到找到字母
            while (l < r && !Character.isLetter(chars[l])) {
                l++;
            }
            // 移动右指针直到找到字母
            while (l < r && !Character.isLetter(chars[r])) {
                r--;
            }
            // 交换字母
            if (l < r) {
                char temp = chars[l];
                chars[l] = chars[r];
                chars[r] = temp;
                l++;
                r--;
            }
        }

        return new String(chars); // 将字符数组转换回字符串
    }
}

3.3 LC 680 验证回文串 II

问题描述

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

提示

• 需要考虑最多删除一个字符后字符串是否可以成为回文。
• 可以使用双指针法，遇到不匹配时尝试删除左边或右边的一个字符。

思路分析

双指针初始化：

• 创建两个指针，l 和 r，分别指向字符串的开始和结束。

双指针遍历

• 使用 while 循环遍历字符串，直到 l < r。
• 在循环中，检查 s.charAt(l) 和 s.charAt(r) 是否相等：
  • 如果相等，继续向内移动指针（l++ 和 r--）。
  • 如果不相等，表示存在一个不匹配的字符。

检查删除字符后的回文：

• 当发现不匹配时，检查两种情况：
  • 删除左边的字符：检查从 s[l+1] 到 s[r] 的子串是否为回文。
  • 删除右边的字符：检查从 s[l] 到 s[r-1] 的子串是否为回文。

回文检查逻辑：

• 使用 while 循环遍历每种子串，比较字符，如果发现不匹配，返回 false。
• 如果能够成功遍历完整个子串，则说明该子串是回文，返回 true。

最终返回：

• 如果在原始字符串的遍历中没有发现不匹配的字符，则说明字符串本身是回文，返回 true。

参考解答

class Solution {
    public boolean validPalindrome(String s) {
        // 首先判断字符串本身是否为回文
        if (isPalindrome(s, 0, s.length() - 1)) {
            return true;
        }

        int l = 0;
        int r = s.length() - 1;

        // 使用双指针从两端向中间遍历
        while (l < r) {
            if (s.charAt(l) == s.charAt(r)) {
                l++;
                r--;
            } else {
                // 尝试删除左边的字符或右边的字符
                return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1);
            }
        }

        return true;
    }

    // 辅助函数：判断给定的子串 s[l:r] 是否为回文
    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

课后练习

题目编号	题目名称	简介
LC151	反转字符串中的单词	给定一个字符串，逐字反转字符串中的单词，去除多余空格。
LC392	判断子序列	给定两个字符串 s 和 t，判断 s 是否是 t 的子序列。
LC541	反转字符串 II	给定一个字符串，按照每隔 k 个字符反转前 k 个字符。
LC1332	删除回文子序列	给定一个字符串，删除回文子序列的最少步骤数。