题目描述

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

样例

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

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

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

注意

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

算法

(模拟) $O(n)$

1. 定义两个指针 i 和 j，初始时指向头和尾，每次 i 都向前移动直到遇到一个字母，同理 j 向后移动，如果 i 小于 j，则交换；
2. 如此循环直到 i 大于等于 j。

时间复杂度

• 每个字符仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅使用了常数的空间。

C++ 代码

class Solution {
public:
    string reverseOnlyLetters(string S) {
        int n = S.length();
        int i = 0, j = n - 1;
        while (i < j) {

            while (!(S[i] >= 'a' && S[i] <= 'z' || S[i] >= 'A' && S[i] <= 'Z'))
                i++;

            while (!(S[j] >= 'a' && S[j] <= 'z' || S[j] >= 'A' && S[j] <= 'Z'))
                j--;

            if (i < j) {
                swap(S[i], S[j]);
                i++;
                j--;
            }
        }
        return S;
    }
};