LeetCode 917 仅仅反转字母 简单

1. XXXXX

1. 917 仅仅反转字母 简单

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

所有非英文字母保留在原有位置。
所有英文字母（小写或大写）位置反转。
返回反转后的 s 。

1. 原题链接

LeetCode 917 仅仅反转字母 简单

2. 题目要求

示例 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 不含 ‘"’ 或 ‘\’

3. 基础框架

● Cpp代码框架

class Solution {
public:
    string reverseOnlyLetters(string s) {
    }
};
1
2
3
4
5

2. 解题思路

1. 思路分析

$(1)$ 只反转字符串中的字母，其他字符位置保持不变；
$(2)$ 利用快排思想，定义两个变量：$l$指向起始位置，$r$指向最后一个字符位置;
$(3)$ $l$向后查找直到找到第一个字母字符的位置，$r$向前查找直到找到第一个字母字符的位置；
注意$l$和$r$在查找过程中需要在有效范围，不在有效范围时则不进行查找查找；
$(4)$ 当$l$小于$r$时，交换$l$和$r$位置上的字母字符，然后$l$自减1，$r$自增1;
$(5)$ 重复$2,3,4$步直到$l$大于$r$为止;

2. 时间复杂度

$O(N)$
$l$向后走，$r$向前走，直到二者相遇，共走了$n$步;

3. 代码实现

class Solution {
public:
    string reverseOnlyLetters(string s) {
        int l = 0;
        int r = s.size() - 1;

        while(l < r){
            while(l < s.size() && !isalpha(s[l])){
                l++;
            }

            while(r >= 0 && !isalpha(s[r])){
                r--;
            }

            if(l < r){
                swap(s[l], s[r]);
                l++;
                r--;
            }
        }
        return s;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24