917. Reverse Only Letters

置顶

Created At : 2021-04-08 10:36

Count:559 Views 👀 :

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://github.com/grandyang/leetcode/issues/917

参考资料：

https://leetcode.com/problems/reverse-only-letters/

https://leetcode.com/problems/reverse-only-letters/discuss/178419/JavaC%2B%2BPython-Two-Pointers

https://leetcode.com/problems/reverse-only-letters/discuss/200878/easy-C%2B%2B-with-comments-two-pointer-based-approach

LeetCode All in One 题目讲解汇总(持续更新中…)

转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com