[LeetCode] 917. Reverse Only Letters

Given a string s, reverse the string according to the following rules:

All the characters that are not English letters remain in the same position.
All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Constraints:

1 <= s.length <= 100
s consists of characters with ASCII values in the range [33, 122].
s does not contain '"' or '\'.

仅仅反转字母。

给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。

思路是逼近型的双指针。我们从 input 字符串的两侧往中间扫描，遇到不是字母的就跳过，遇到两边都是字母的才做交换的操作。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public String reverseOnlyLetters(String s) {
 3         StringBuilder sb = new StringBuilder(s);
 4         int i = 0;
 5         int j = s.length() - 1;
 6         while (i < j) {
 7             if (!Character.isLetter(sb.charAt(i))) {
 8                 i++;
 9             } else if (!Character.isLetter(sb.charAt(j))) {
10                 j--;
11             } else {
12                 char temp = sb.charAt(i);
13                 sb.setCharAt(i, sb.charAt(j));
14                 sb.setCharAt(j, temp);
15                 i++;
16                 j--;
17             }
18         }
19         return sb.toString();
20     }
21 }

LeetCode 题目总结