题目
难度：★☆☆☆☆
类型：字符串
给定一个字符串 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)
如有疑问或建议，欢迎评论区留言~
