大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

对字符串进行逆序，要求只把字母的顺序翻转，而其他字符原地不动。

解题方法

本文提供了三种解法：栈、单指针、双指针。

栈

看到逆序，有没有想到栈？栈是一种「先进后出」的数据结构，因此可以实现逆序。

  1. 先把所有的字母保存到栈中；
  2. 遍历字符串 S，当前遍历到 $i$ 位置:
    1. 如果 $S[i]$ 是字母，则往结果字符串中添加栈顶元素
    2. 否则，添加 $S[i]$
  1. class Solution(object):
  2.     def reverseOnlyLetters(self, S):
  3.         """
  4.         :type S: str
  5.         :rtype: str
  6.         """
  7.         letters = []
  8.         N = len(S)
  9.         for i, s in enumerate(S):
  10.             if s.isalpha():
  11.                 letters.append(s)
  12.         res = ""
  13.         for i, s in enumerate(S):
  14.             if s.isalpha():
  15.                 res += letters.pop()
  16.             else:
  17.                 res += s
  18.         return res

复杂度分析：

  1. 时间复杂度：$O(N)$
  2. 空间复杂度：$O(N)$

    双指针

其实这道题标准的解法是双指针。

  1. 使用两个指针 $left$ 和 $right$ 分别指向前面和后面的两个字母，非字母就跳过。
  2. 然后将两个字母交换位置。
  3. 当 $left >= right$ 时，结束。

这个做法需要注意，需要始终满足 $left >= right$，因此在 while 和 if 中都做了判断。

  1. class Solution(object):
  2.     def reverseOnlyLetters(self, S):
  3.         """
  4.         :type S: str
  5.         :rtype: str
  6.         """
  7.         N = len(S)
  8.         left, right = 0, N - 1
  9.         slist = list(S)
  10.         while left < right:
  11.             while left < right and (not S[left].isalpha()):
  12.                 left += 1
  13.             while right >= left and (not S[right].isalpha()):
  14.                 right -= 1
  15.             if left < right:
  16.                 slist[left], slist[right] = slist[right], slist[left]
  17.             left, right = left + 1, right - 1
  18.         return "".join(slist)

时间复杂度：

  • 时间复杂度：917. 仅仅反转字母 - 图1，其中 917. 仅仅反转字母 - 图2 是数组长度；
  • 空间复杂度： 917. 仅仅反转字母 - 图3#card=math&code=O%281%29&id=Pz3XE)

总结

  1. 栈的做法用到了额外空间，双指针做法是在原地修改。
  2. 属于经典的双指针题目了，希望对你有帮助。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。