LC 0917.Reverse Only Letters

题目描述

这是 LeetCode 上的 917. 仅仅反转字母 ，难度为简单。

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

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

返回反转后的 s 。

示例 1：

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

示例 2：

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

示例 3：

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

提示

• 1 <= s.length <= 100
• s 仅由 ASCII 值在范围 [33, 122] 的字符组成
• s 不含 '\"' 或 '\\'

解答

方法一：双指针

根据题目，分别从字符串的两端开始遍历，遇到字母就交换两个字母，否则继续遍历直到两个指针相遇。

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

• 时间复杂度：\(O(N)\)，其中 N 为字符串的长度。

• 空间复杂度：\(O(N)\)，调用 toCharArray 和构造新字符串均需要与字符串长度等同的空间。

每题一图