题目

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

示例：

输入：s = "ab-cd"

输出："dc-ba"

解答

普通解法

依次遍历字符串 s ，通过栈保存每一个字母元素，然后再次遍历，将是字母元素的位置替换为出栈元素。

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int n = s.size();
        stack<char> st;

        for (int i = 0; i < n; ++i) {
            if ((s[i] >= 'a' && s[i] <= 'z') ||
                (s[i] >= 'A' && s[i] <= 'Z')) {
                st.push(s[i]);
            }
        }

        for (int i = 0; i < n; ++i) {
            if ((s[i] >= 'a' && s[i] <= 'z') ||
                (s[i] >= 'A' && s[i] <= 'Z')) {
                auto get = st.top();
                st.pop();
                s[i] = get;
            }
        }

        return s;
    }
};

双指针

通过左右指针，依次从最左侧和最右侧遍历字符串 s,如果l和r指向的均为字母，则互换内容，并继续遍历，知道l和r重合。

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int n = s.size();

        // 双指针
        int l = 0;
        int r = n - 1;

        while (l < r) {
            while ((l < r) && !((s[l] >= 'a' && s[l] <= 'z') || (s[l] >= 'A' && s[l] <= 'Z'))) {
                l++;
            }
            while ((l < r) && !((s[r] >= 'a' && s[r] <= 'z') || (s[r] >= 'A' && s[r] <= 'Z'))) {
                r--;
            }

            if (l < r) {
                auto tmp = s[l];
                s[l++] = s[r];
                s[r] = tmp;
                r--;
            }
        }

        return s;
    }
};