【LeetCode笔记 - 每日一题】917. 仅仅反转字母（Java、字符串、双指针、栈）

917. 仅仅反转字母

题目描述：

字符串中，非字母不移动，字母（包括大、小写）顺序反转。

思路 & 代码：

1、 用stack，一开始没弄清for-each的顺序，在纠结toCharArray()变成数组后，顺序是不是要反过来，即从数组下标为0的元素开始遍历。最后确定还是和字符串一样，从左到右。所以使用stack而不是queue（当然API都用的是Deque）还复习了Character类中的isLetter()方法，此外还有isDigit()、isUpperCase()、isLowerCase()等。

O(n) 的时间和空间

class Solution {
    public String reverseOnlyLetters(String s) {
        StringBuilder sb = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        char[] ca = s.toCharArray();
        for (char c : ca) {
            if (!Character.isLetter(c)) continue;
            stack.push(c);
        }
        for (char c : ca) {
            if (!Character.isLetter(c)) sb.append(c);
            else sb.append(stack.pop());
        }
        return sb.toString();
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了43.97%的用户

内存消耗：39.7 MB, 在所有 Java 提交中击败了5.46%的用户

通过测试用例：115 / 115

2、题解区三叶大佬：双指针，找到需要交换的两个字符才swap()

p.s. 可以放心的使用 new String(char[]) 另一个API性能一样

易错点是swap之后也要移动指针

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

作者：AC_OIer
链接：https://leetcode-cn.com/problems/reverse-only-letters/solution/gong-shui-san-xie-jian-dan-shuang-zhi-zh-xrpt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。