Description
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 <= 100s consists of characters with ASCII values in the range [33, 122].s does not contain '\"' or '\\'.
Solutions
Solution 1: Two Pointers
We use two pointers i and j to point to the head and tail of the string respectively. When i < j, we continuously move i and j until i points to an English letter and j points to an English letter, then we swap s[i] and s[j]. Finally, we return the string.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.
PythonJavaC++GoTypeScriptRust
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
cs = list(s)
i, j = 0, len(cs) - 1
while i < j:
while i < j and not cs[i].isalpha():
i += 1
while i < j and not cs[j].isalpha():
j -= 1
if i < j:
cs[i], cs[j] = cs[j], cs[i]
i, j = i + 1, j - 1
return "".join(cs)(code-box)
class Solution {
public String reverseOnlyLetters(String s) {
char[] cs = s.toCharArray();
int i = 0, j = cs.length - 1;
while (i < j) {
while (i < j && !Character.isLetter(cs[i])) {
++i;
}
while (i < j && !Character.isLetter(cs[j])) {
--j;
}
if (i < j) {
char t = cs[i];
cs[i] = cs[j];
cs[j] = t;
++i;
--j;
}
}
return new String(cs);
}
}(code-box)
class Solution {
public:
string reverseOnlyLetters(string s) {
int i = 0, j = s.size() - 1;
while (i < j) {
while (i < j && !isalpha(s[i])) {
++i;
}
while (i < j && !isalpha(s[j])) {
--j;
}
if (i < j) {
swap(s[i++], s[j--]);
}
}
return s;
}
};(code-box)
func reverseOnlyLetters(s string) string {
cs := []rune(s)
i, j := 0, len(s)-1
for i < j {
for i < j && !unicode.IsLetter(cs[i]) {
i++
}
for i < j && !unicode.IsLetter(cs[j]) {
j--
}
if i < j {
cs[i], cs[j] = cs[j], cs[i]
i++
j--
}
}
return string(cs)
}(code-box)
function reverseOnlyLetters(s: string): string {
const cs = [...s];
let [i, j] = [0, cs.length - 1];
while (i < j) {
while (!/[a-zA-Z]/.test(cs[i]) && i < j) {
i++;
}
while (!/[a-zA-Z]/.test(cs[j]) && i < j) {
j--;
}
[cs[i], cs[j]] = [cs[j], cs[i]];
i++;
j--;
}
return cs.join('');
}(code-box)
impl Solution {
pub fn reverse_only_letters(s: String) -> String {
let mut cs: Vec<char> = s.chars().collect();
let n = cs.len();
let mut l = 0;
let mut r = n - 1;
while l < r {
if !cs[l].is_ascii_alphabetic() {
l += 1;
} else if !cs[r].is_ascii_alphabetic() {
r -= 1;
} else {
cs.swap(l, r);
l += 1;
r -= 1;
}
}
cs.iter().collect()
}
}(code-box)
