3823. 反转一个字符串里的字母后反转特殊字符

🎯 问题描述（来源于LeetCode）

描述：
给定一个字符串 s，该字符串只包含小写字母和特殊字符 "!@#$%^&*()"。
请先反转字符串中所有字母的顺序（但保持字母在原字母位置），再反转所有特殊字符的顺序（保持特殊字符在原来特殊字符位置），然后返回结果字符串。

说明：

字母和特殊字符互不干扰，各自反转。
反转是指将同类字符的顺序倒置。

示例：

示例 1：

输入: s = ")ebc#da@f("
输出: "(fad@cb#e)"
解释: 
  1. 提取字母 "ebc daf"？实际上字母按顺序为 e,b,c,d,a,f → 反转后 f,a,d,c,b,e。
  2. 特殊字符顺序为 ),#,@,( → 反转后 (, @, #, )。
  3. 填充后得到 "(fad@cb#e)"。

示例 2：

1 2	输入: s = "z" 输出: "z"

示例 3：

1 2	输入: s = "!@#$%^&()" 输出: ")(&^%$#@!"

💻 解题思路

思路：双指针分两轮反转（通用方法）

算法步骤

将字符串转为列表 t，便于原地修改。
定义通用函数 reverse(t, f)，其中 f 是一个判断函数，用于保护某些字符不参与交换：
- 设置左右指针 i=0，j=len(t)-1。
- 当 i < j 时：
  - 左指针跳过满足 f 的字符（即保护该类字符）。
  - 右指针跳过满足 f 的字符。
  - 交换左右指针所指的字符（这两个字符都不满足 f，即属于另一类）。
  - 移动指针。
- 该函数的效果是：将所有不满足 f 的字符进行反转，而满足 f 的字符保持位置不变。
第一轮：调用 reverse(t, str.islower)，保护小写字母，反转特殊字符。
第二轮：调用 reverse(t, lambda ch: not ch.islower())，保护特殊字符，反转小写字母。
返回列表转字符串。

代码实现（您的代码）

from typing import List, Callable

class Solution:
    def reverse(self, t: List[str], f: Callable[[str], bool]) -> None:
        i, j = 0, len(t) - 1
        while i < j:
            while i < j and f(t[i]):
                i += 1
            while i < j and f(t[j]):
                j -= 1
            t[i], t[j] = t[j], t[i]
            i += 1
            j -= 1

    def reverseByType(self, s: str) -> str:
        t = list(s)
        self.reverse(t, str.islower)          # 反转非小写（即特殊字符）
        self.reverse(t, lambda ch: not ch.islower())  # 反转小写字母
        return ''.join(t)

📊 性能分析

时间复杂度： $O(n)$ ，两次遍历，每次 $O(n)$ 。
空间复杂度： $O(n)$ ，列表存储字符串。

思考

您的解法通过两轮反转，巧妙地实现了分别反转两类字符的需求。在第一轮中，保护小写字母（str.islower 返回 True），于是所有非小写字符（特殊字符）被反转；第二轮保护非小写字符（not ch.islower() 返回 True），于是小写字母被反转。这种“保护-反转”模式通用且高效，避免了显式提取和填充。虽然相较于提取反转再填回的方法，它的理解成本稍高，但代码简洁，且原地操作节省了额外列表。对于本题，两种方法均可，您的实现展现了双指针的灵活运用。