题目

难度：★☆☆☆☆
类型：字符串

给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

提示
S.length <= 100
33 <= S[i].ASCIIcode <= 122
S 中不包含 \ or "

示例

示例 1
输入："ab-cd"
输出："dc-ba"

示例 2
输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例 3
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

解答

方案1：哈希表

我们使用字典记录每个字符所在的位置，然后找出所有字母字符的位置并组成列表，将该列表逆序更新原字典，相当于只在有字母的位置上做字符串逆序，使用更新后的字典构建字母逆序的字符串。

class Solution:
    def reverseOnlyLetters(self, S):
        """
        :param S: str
        :return: str
        """
        loc = {i: c for i, c in enumerate(S)}
        alpha = {i: c for i, c in loc.items() if c.isalpha()}
        reversed_alpha = {i: c for i, c in zip(reversed(list(alpha.keys())), alpha.values())}
        loc.update(reversed_alpha)
        return ''.join([loc[i] for i in range(len(S))])

方案2：双指针

我们定义左右指针，并初始化为字符串两端字符所在位置，然后两个指针逐渐向中间靠拢，当两个指针同时找到字母时，交换两指针处的字符，如果只有一个指针处是字母，那么另一个指针要继续移动，直到找到字母。循环控制条件是左指针不能到右指针右边。

class Solution:
    def reverseOnlyLetters(self, S):
        """
        :param S: str
        :return: str
        """

        S = list(S)
        left, right = 0, len(S)-1
        while left < right:
            if not S[left].isalpha():
                left += 1
            elif not S[right].isalpha():
                right -= 1
            else:
                S[left], S[right] = S[right], S[left]
                left += 1
                right -= 1
        return ''.join(S)

如有疑问或建议，欢迎评论区留言~