Easy

题目描述

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

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

返回反转后的 s 。

示例 1：

输入: s = "ab-cd"
输出: "dc-ba"

示例 2：

输入: s = "a-bC-dEf-ghIj"
输出: "j-Ih-gfE-dCba"

示例 3：

输入: s = "Test1ng-Leet=code-Q!"
输出: "Qedo1ct-eeLg=ntse-T!"

提示：

  • 1 <= s.length <= 100
  • s 由 ASCII 值在范围 [33, 122] 的字符组成
  • s 不含 '\"' 或 '\\'

解题思路

解题思路

这道题要求仅仅反转字符串中的英文字母，而非字母字符保持原位置不变。

方法一：双指针法（推荐）

使用双指针从字符串两端向中间移动：

  1. 左指针从左侧寻找英文字母，右指针从右侧寻找英文字母
  2. 当两个指针都找到字母时，交换它们的位置
  3. 继续移动指针，直到两指针相遇

这种方法时间复杂度最优，空间复杂度也最小。

方法二：栈辅助法

先遍历字符串，将所有字母压入栈中，然后再次遍历字符串，遇到字母位置就从栈中弹出元素替换。

方法三：额外数组法

将字符串转为字符数组，提取所有字母并反转，然后按原顺序填回字母位置。

双指针法是最优解，因为它原地操作，不需要额外的数据结构。

代码实现

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int left = 0, 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;
    }
};

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        s = list(s)
        left, right = 0, len(s) - 1
        
        while left < right:
            # 左指针寻找字母
            while left < right and not s[left].isalpha():
                left += 1
            # 右指针寻找字母
            while left < right and not s[right].isalpha():
                right -= 1
            # 交换字母
            if left < right:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
        
        return ''.join(s)

public class Solution {
    public string ReverseOnlyLetters(string s) {
        char[] chars = s.ToCharArray();
        int left = 0, right = s.Length - 1;
        
        while (left < right) {
            // 左指针寻找字母
            while (left < right && !char.IsLetter(chars[left])) {
                left++;
            }
            // 右指针寻找字母
            while (left < right && !char.IsLetter(chars[right])) {
                right--;
            }
            // 交换字母
            if (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        
        return new string(chars);
    }
}

var reverseOnlyLetters = function(s) {
    const chars = s.split('');
    let left = 0, right = s.length - 1;
    
    while (left < right) {
        // 左指针寻找字母
        while (left < right && !isLetter(chars[left])) {
            left++;
        }
        // 右指针寻找字母
        while (left < right && !isLetter(chars[right])) {
            right--;
        }
        // 交换字母
        if (left < right) {
            [chars[left], chars[right]] = [chars[right], chars[left]];
            left++;
            right--;
        }
    }
    
    return chars.join('');
    
    function isLetter(char) {
        return (char >= 'a' && char <= 'z') || (char >= 'A' && char <= 'Z');
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1) 对于C++；O(n) 对于其他语言（字符串不可变需要转换为数组）

其中 n 为字符串长度。每个字符最多被访问一次，时间复杂度为 O(n)。C++ 可以直接修改字符串，空间复杂度为 O(1)；其他语言由于字符串不可变特性，需要额外的字符数组空间。

相关题目