[LeetCode] 917. Reverse Only Letters
grandyang opened this issue · 0 comments
grandyang commented
Given a string S
, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.
Example 1:
Input: "ab-cd"
Output: "dc-ba"
Example 2:
Input: "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"
Example 3:
Input: "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"
Note:
S.length <= 100
33 <= S[i].ASCIIcode <= 122
S
doesn't contain\
or"
这道题给了一个由字母和其他字符组成的字符串,让我们只翻转其中的字母,并不是一道难题,解题思路也比较直接。可以先反向遍历一遍字符串,只要遇到字母就直接存入到一个新的字符串 res,这样就实现了对所有字母的翻转。但目前的 res 中就只有字母,还需要将原字符串S中的所有的非字母字符加入到正确的位置,可以再正向遍历一遍原字符串S,遇到字母就跳过,否则就把非字母字符加入到 res 中对应的位置,参见代码如下:
解法一:
class Solution {
public:
string reverseOnlyLetters(string S) {
string res = "";
for (int i = (int)S.size() - 1; i >= 0; --i) {
if (isalpha(S[i])) res.push_back(S[i]);
}
for (int i = 0; i < S.size(); ++i) {
if (isalpha(S[i])) continue;
res.insert(res.begin() + i, S[i]);
}
return res;
}
};
再来看一种更加简洁的解法,使用两个指针i和j,分别指向S串的开头和结尾。当i指向非字母字符时,指针i自增1,否则若j指向非字母字符时,指针j自减1,若i和j都指向字母时,则交换 S[i] 和 S[j] 的位置,同时i自增1,j自减1,这样也可以实现只翻转字母的目的,参见代码如下:
解法二:
class Solution {
public:
string reverseOnlyLetters(string S) {
int n = S.size(), i = 0, j = n - 1;
while (i < j) {
if (!isalpha(S[i])) ++i;
else if (!isalpha(S[j])) --j;
else {
swap(S[i], S[j]);
++i; --j;
}
}
return S;
}
};
Github 同步地址:
参考资料:
https://leetcode.com/problems/reverse-only-letters/
https://leetcode.com/problems/reverse-only-letters/discuss/178419/JavaC%2B%2BPython-Two-Pointers