难度: 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 <= 100s 仅由 ASCII 值在范围 [33, 122] 的字符组成s 不含 '\"' 或 '\\'运行时间: 22 ms
内存: 16.0 MB
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
s_list=list(s)
reversed_string=[""]*len(s)
left,right=0,len(s)-1
while left<=right:
if not s[left].isalpha():
reversed_string[left]=s[left]
left+=1
elif not s[right].isalpha():
reversed_string[right]=s[right]
right-=1
else:
reversed_string[left],reversed_string[right]=s[right],s[left]
left+=1
right-=1
return ''.join(reversed_string)
题解采用双指针技术，分别从字符串的首尾开始遍历。左指针left从前向后移动，右指针right从后向前移动。如果左指针指向的字符不是字母，则将该字符直接复制到结果中并移动左指针。如果右指针指向的字符不是字母，则将该字符直接复制到结果中并移动右指针。当左右指针均指向字母时，将它们的位置互换，即将右指针的字母放到左指针的位置，左指针的字母放到右指针的位置，然后同时移动两个指针。这个过程一直进行，直到left大于right为止。最后，将结果数组转换为字符串形式返回。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
s_list = list(s) # 将字符串转换为列表以便修改
reversed_string = [''] * len(s) # 创建一个与原字符串等长的空字符列表
left, right = 0, len(s) - 1 # 初始化左右指针
while left <= right:
if not s[left].isalpha(): # 左指针指向非字母
reversed_string[left] = s[left]
left += 1 # 移动左指针
elif not s[right].isalpha(): # 右指针指向非字母
reversed_string[right] = s[right]
right -= 1 # 移动右指针
else:
# 交换左右指针指向的字母
reversed_string[left], reversed_string[right] = s[right], s[left]
left += 1 # 同时移动左右指针
right -= 1
return ''.join(reversed_string) # 将列表转换回字符串并返回
双指针方法是解决这个问题的一种高效方式，因为它允许同时从字符串的两端向中心移动，仅需遍历一次字符串即可完成所有字母的反转。使用单指针方法虽然可行，但通常需要两次遍历：一次收集所有字母，一次放置反转后的字母，效率较低。其他方法如使用栈也可以实现，但相对于直接在原字符串上操作，使用额外的数据结构可能会增加空间复杂度。因此，双指针既节省时间也节省空间，是解决此问题的理想选择。
即使左右指针指向相同的字母，如'aa'，交换操作仍会进行，但这并不会影响算法的总体效率。虽然这看起来是冗余的操作，因为交换相同的字符并不会改变字符串的状态，但这种情况的处理并不会引入额外的时间复杂度，因为每次操作仍然是常数时间内完成。因此，尽管存在这种看似冗余的操作，它并不会显著影响算法的效率。
是的，这种处理方式确实可以保证所有的英文字母都被正确反转。算法通过移动两个指针，跳过非字母字符，只有当两个指针都指向字母时才进行交换。这确保了即使字母被非字母字符隔开，它们仍然会与字符串中相对应位置的字母交换位置。因此，无论字母之间的间隔如何，所有的字母最终都会被反转到正确的位置。