README.md

917. Reverse Only Letters

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 "

Solutions (Python)

1. Two Pointers

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        S = list(S)
        i, j = 0, len(S) - 1

        while i < j:
            if S[i].isalpha() and S[j].isalpha():
                S[i], S[j] = S[j], S[i]
                i += 1
                j -= 1
            elif not S[i].isalpha():
                i += 1
            elif not S[j].isalpha():
                j -= 1

        return ''.join(S)

2. Stack

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        stack = []
        ret = ""

        for ch in S:
            if ch.isalpha():
                stack.append(ch)

        for ch in S:
            if ch.isalpha():
                ret += stack.pop()
            else:
                ret += ch

        return ret