Formatted question description: https://leetcode.ca/all/917.html

# 917. Reverse Only Letters (Easy)

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:

1. S.length <= 100
2. 33 <= S[i].ASCIIcode <= 122
3. S doesn't contain \ or "

Companies:
Microsoft

Related Topics:
String

## Solution 1.

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

// Time: O(N)
// Space: O(1)
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;
}
};


Java

class Solution {
public String reverseOnlyLetters(String S) {
char[] array = S.toCharArray();
int low = 0, high = array.length - 1;
while (low < high) {
char c1 = array[low], c2 = array[high];
if (Character.isLetter(c1) && Character.isLetter(c2)) {
array[low] = c2;
array[high] = c1;
low++;
high--;
} else {
if (!Character.isLetter(c1))
low++;
if (!Character.isLetter(c2))
high--;
}
}
return new String(array);
}
}