Skip to content

Lesson9 字符串双指针算法专题

目录

  1. 对撞指针

  2. 例题讲解

  3. 举一反三

  4. 课后练习

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

1. 对撞指针

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

对撞指针

1.1 对撞指针解题步骤

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

1.2 对撞指针伪代码模版

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int left = 0;
int right = len(nums) - 1;

while (left < right) {
    if (满足某些条件) {
        return 符合条件的值;
    }
    if (条件1) {
        left++;  // 移动左指针
    } else {
        right--;  // 移动右指针
    }
}
return -1;  // 如果没找到，返回标记值

1.3 对撞指针适用范围

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

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

2. 例题讲解

LC 344 反转字符串

问题描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须 原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

题目分析

对于长度为 N 的字符数组，反转的过程就是将前后的字符交换，直到两端的指针相遇为止。具体来说：

  1. 双指针法：
    • 初始化两个指针，start 指向字符串的第一个字符，end 指向最后一个字符。
    • 当 start < end 时，交换这两个位置的字符，然后 start 指针右移，end 指针左移，直到两个指针相遇或交错。

思路

  1. 双指针思路：
    • 将 start 设置为 0，end 设置为 s.size() - 1。
    • 当 start 小于 end 时，交换 s[start] 和 s[end]，然后分别移动两个指针。
    • 当 start >= end 时，说明字符串已经反转完成。

参考解答

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    void reverseString(vector<char>& s) {
        int start = 0;
        int end = s.size() - 1;
        while (start < end) {
            swap(s[start], s[end]); // 交换 start 和 end 位置的字符
            start++;
            end--;
        }
    }
};

要点说明：

  • 双指针法： 使用 start 和 end 两个指针从字符串的两端向中间移动，并交换相应位置的字符。
  • 原地修改： 在给定的 vector<char>& 中直接进行操作，没有使用额外的空间。

LC 125 验证回文串

问题描述

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

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

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

提示

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

思路分析

  1. 过滤非字母数字字符：

    • 使用 isalnum 函数来检查字符是否为字母或数字。
    • 跳过不属于字母数字的字符。

  2. 双指针法：

    • 使用两个指针，一个指向字符串的开头，另一个指向字符串的结尾。
    • 从两端开始向中间移动，逐个比较有效的字符。

  3. 忽略大小写：

    • 使用 tolower 或 toupper 函数来忽略大小写差异。

参考解答

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isPalindrome(string s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            // 移动 start 指针跳过非字母数字字符
            if (!isalnum(s[start])) {
                start++;
                continue;
            }
            // 移动 end 指针跳过非字母数字字符
            if (!isalnum(s[end])) {
                end--;
                continue;
            }
            // 忽略大小写比较字符
            if (tolower(s[start]) != tolower(s[end])) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
};

切片法

可以通过预处理将字符串转换为只包含字母和数字的小写形式，然后判断这个处理后的字符串是否是回文。

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char c : s) {
            if (isalnum(c)) {
                sgood += tolower(c);
            }
        }
        // 检查 sgood 是否是回文
        int start = 0, end = sgood.length() - 1;
        while (start < end) {
            if (sgood[start] != sgood[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
};

要点说明：

  • 使用 isalnum 判断是否是字母或数字。
  • 使用 tolower 将字符转换为小写进行比较。
  • 采用双指针法，直接对原字符串进行判断，符合空间复杂度要求。

3. 举一反三

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

问题描述

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

元音字母 包括 'a'、'e'、'i'、'o'、'u'，并且大小写字母均视为元音字母。

提示

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

思路分析

我们可以使用 双指针法 对字符串中的元音字母进行反转。思路如下：

  1. 初始化两个指针：

    • 一个指针 start 指向字符串的首位，另一个指针 end 指向字符串的末位。

  2. 元音字母的检查：

    • 如果 start 和 end 所指字符都是元音字母，则交换它们，并将 start 向右移，end 向左移。
    • 如果 start 指向的字符不是元音字母，则向右移。
    • 如果 end 指向的字符不是元音字母，则向左移。

  3. 继续检查直到 start >= end。

参考解答

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string reverseVowels(string s) {
        string vowels = "aeiouAEIOU";
        int start = 0;
        int end = s.length() - 1;

        while (start < end) {
            // 用 while 循环找到最近的元音字母
            while (start < end && vowels.find(s[start]) == string::npos) {
                start++;
            }
            while (start < end && vowels.find(s[end]) == string::npos) {
                end--;
            }
            // 交换元音字母
            if (start < end) {
                swap(s[start], s[end]);
                start++;
                end--;
            }
        }
        return s;
    }
};

说明

  • vowels.find(s[start]) != string::npos：用于检查字符 s[start] 是否在 vowels 字符串中，表示这是一个元音字母。
  • swap(s[start], s[end])：交换两个元音字符。
  • 双指针的移动逻辑确保只有元音字母被反转，其他字符保持原位置不变。

LC 917 仅仅反转字母

问题描述

给定一个字符串 s，根据下述规则反转字符串中的字母：

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

返回反转后的字符串 s。

提示

  • 你只需要反转字母，非字母字符的位置保持不变。
  • 使用双指针法可以高效地遍历和交换字母。

思路分析

使用 双指针法 来处理字母反转。具体思路如下：

  1. 双指针初始化：

    • 指针 left 从字符串左侧开始，指针 right 从字符串右侧开始。

  2. 寻找字母并交换：

    • left 向右移动，跳过非字母字符，直到找到一个字母。
    • right 向左移动，跳过非字母字符，直到找到一个字母。
    • 当 left < right 时，交换这两个字母的位置，继续移动指针。

  3. 停止条件：

    • 当 left >= right 时，表示所有字母都已反转，退出循环。

参考解答

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string reverseOnlyLetters(string s) {
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // 跳过左边的非字母字符
            while (left < right && !isalpha(s[left])) {
                left++;
            }
            // 跳过右边的非字母字符
            while (left < right && !isalpha(s[right])) {
                right--;
            }
            // 交换字母
            if (left < right) {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        return s;
    }
};

解释

  1. isalpha(s[left])：检查字符是否是字母，跳过非字母字符。
  2. swap(s[left], s[right])：交换 left 和 right 位置的字母。
  3. 双指针从两端向中间移动，反转字符串中的字母，非字母字符不受影响。

LC 680 验证回文串

问题描述

给定一个字符串 s，最多可以删除其中的一个字符。请判断删除一个字符后，字符串是否能成为回文串。如果能成为回文串，返回 true；否则，返回 false。

提示

  • 需要考虑在删除最多一个字符的情况下，字符串能否成为回文。
  • 使用双指针法，在遇到不匹配的字符时，尝试删除左边或右边的一个字符，并检查剩余部分是否为回文。

思路分析

  1. 双指针法：

    • 从字符串的两端使用两个指针 start 和 end，逐字符向中间移动，检查是否是回文。

  2. 处理不匹配字符：

    • 当 s[start] 和 s[end] 不相等时，可以尝试跳过一个字符（删除），并判断剩下的字符串是否是回文。
    • 可以选择删除左边的字符（即 start+1 到 end 的子串）或右边的字符（即 start 到 end-1 的子串）来继续验证。

  3. 辅助函数 helper：

    • 用于判断给定子串是否是回文串。

参考解答

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    // 辅助函数，判断子串是否为回文
    bool helper(string s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    bool validPalindrome(string s) {
        int start = 0;
        int end = s.length() - 1;

        while (start < end) {
            // 当遇到不匹配的字符时，尝试跳过一个字符
            if (s[start] != s[end]) {
                // 尝试跳过左边字符或右边字符后，检查是否为回文
                return helper(s, start + 1, end) || helper(s, start, end - 1);
            }
            start++;
            end--;
        }

        return true;
    }
};

说明

  1. helper 函数：用于判断字符串 s 中从 start 到 end 是否为回文。
  2. 主函数 validPalindrome：使用双指针遍历字符串，遇到不匹配时，分别尝试跳过左边或右边的字符，并调用 helper 判断剩余部分是否为回文。
  3. 如果在不删除字符的情况下，字符串已经是回文，则直接返回 true。

课后练习

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