LeetCode 917 仅仅反转字母 简单
题目 - 点击直达
- 1. XXXXX
- 1. 917 仅仅反转字母 简单
- 1. 原题链接
- 2. 题目要求
- 3. 基础框架
- 2. 解题思路
- 1. 思路分析
- 2. 时间复杂度
- 3. 代码实现
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) {
}
};
2. 解题思路
1. 思路分析
(
1
)
(1)
(1) 只反转字符串中的字母，其他字符位置保持不变；
(
2
)
(2)
(2) 利用快排思想，定义两个变量：
l
l
l指向起始位置，
r
r
r指向最后一个字符位置;
(
3
)
(3)
(3)
l
l
l向后查找直到找到第一个字母字符的位置，
r
r
r向前查找直到找到第一个字母字符的位置；
注意
l
l
l和
r
r
r在查找过程中需要在有效范围，不在有效范围时则不进行查找查找；
(
4
)
(4)
(4) 当
l
l
l小于
r
r
r时，交换
l
l
l和
r
r
r位置上的字母字符，然后
l
l
l自减1，
r
r
r自增1;
(
5
)
(5)
(5) 重复
2
,
3
,
4
2,3,4
2,3,4步直到
l
l
l大于
r
r
r为止;
2. 时间复杂度
O
(
N
)
O(N)
O(N)
l
l
l向后走，
r
r
r向前走，直到二者相遇，共走了
n
n
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;
}
};