917 Reverse Only Letters 仅仅反转字母

Description:
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:

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:

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

题目描述:
给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

示例 :

示例 1：

输入："ab-cd"
输出："dc-ba"

示例 2：

输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例 3：

输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

提示：

S.length <= 100
33 <= S[i].ASCIIcode <= 122
S 中不包含 \ or "

思路:

双指针法
时间复杂度O(n), 空间复杂度O(1)

代码:
C++:

class Solution 
{
public:
    string reverseOnlyLetters(string S) 
    {
        int i = 0, j = S.size() - 1;
        while (i < j)
        {
            while (!isalpha(S[i]) and i < j) i++;     
            while (!isalpha(S[j]) and i < j) j--;
            if (i < j) swap(S[i++], S[j--]);
        }
        return S;
    }
};

Java:

class Solution {
    public String reverseOnlyLetters(String S) {
        char[] c = S.toCharArray();
        int i = 0, j = c.length - 1;
        while (i < j) {
            while (!Character.isLetter(c[i]) && i < j) i++;
            while (!Character.isLetter(c[j]) && i < j) j--;
            if (i < j) {
                c[i] ^= c[j];
                c[j] ^= c[i];
                c[i++] ^= c[j--];
            }
        }
        return new String(c);
    }
}

Python:

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        i, j, S = 0, len(S) - 1, list(S)
        while i < j:
            while not S[i].isalpha() and i < j:
                i += 1
            while not S[j].isalpha() and i < j:
                j -= 1
            if i < j:
                S[i], S[j] = S[j], S[i]
                i += 1
                j -= 1
        return ''.join(S)