# 917. Reverse Only Letters 仅仅反转字母

@TOC

## # 题目描述

Given a string `S`, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

``````Input: "ab-cd"
Output: "dc-ba"
``````

Example 2:

``````Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"
``````

Example 3:

``````Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
``````

Note:

1. S.length <= 100
2. 33 <= S[i].ASCIIcode <= 122
3. S doesn't contain \ or "

## # 解题方法

### # 栈

``````class Solution(object):
def reverseOnlyLetters(self, S):
"""
:type S: str
:rtype: str
"""
letters = []
N = len(S)
for i, s in enumerate(S):
if s.isalpha():
letters.append(s)
res = ""
for i, s in enumerate(S):
if s.isalpha():
res += letters.pop()
else:
res += s
return res
``````

### # 单指针

``````class Solution(object):
def reverseOnlyLetters(self, S):
"""
:type S: str
:rtype: str
"""
N = len(S)
l = N - 1
res = ""
for i, s in enumerate(S):
if s.isalpha():
while not S[l].isalpha():
l -= 1
res += S[l]
l -= 1
else:
res += s
return res
``````

### # 双指针

``````class Solution(object):
def reverseOnlyLetters(self, S):
"""
:type S: str
:rtype: str
"""
N = len(S)
left, right = 0, N - 1
slist = list(S)
while left < right:
while left < N and (not S[left].isalpha()):
left += 1
while right >= 0 and (not S[right].isalpha()):
right -= 1
if left < N and right >= 0 and left < right:
slist[left], slist[right] = slist[right], slist[left]
left, right = left + 1, right - 1
return "".join(slist)
``````

## # 日期

2018 年 10 月 7 日 —— 假期最后一天！！