### 题目

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 "

### 把非字母的字符抽出来

Test1ng-Leet=code-Q!    -->     TestngLeetcodeQ


    abcd
/  \
cd    ab
|    |
dc    ba


#### 代码

class Solution {
public String reverseOnlyLetters(String S) {
washStr(S);
StringBuilder reversed = reverse(cleanSb);
for (int i = 0; i < poc; i++) {
reversed.insert(otherCharsOffset[i], otherChars[i]);
}
return reversed.toString();
}

private StringBuilder cleanSb;
private char[] otherChars;
private int poc;
private int[] otherCharsOffset;
private int poco;

// assertion: sb != null
private StringBuilder reverse(StringBuilder sb) {
int len = sb.length();
if (len <= 1) return sb;
if (len == 2) {
char last = sb.charAt(1);
sb.deleteCharAt(1);
sb.insert(0, last);
return sb;
}
int mid = (sb.length() - 1) / 2;
StringBuilder left = reverse(new StringBuilder(sb.substring(0, mid + 1)));
StringBuilder right = reverse(new StringBuilder(sb.substring(mid + 1)));
return right.append(left);
}

private void washStr(String str) {
cleanSb = new StringBuilder();
int len = str.length();
otherChars = new char[len];
poc = 0;
otherCharsOffset = new int[len];
poco = 0;
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
if (Character.isLetter(c)) {
cleanSb.append(c);
} else {
otherChars[poc++] = c;
otherCharsOffset[poco++] = i;
}
}
}
}


### 也可以直接用Character.reverse()库函数

#### 代码

class Solution {
public String reverseOnlyLetters(String S) {
washStr(S);
StringBuilder reversed = cleanSb.reverse();
for (int i = 0; i < poc; i++) {
reversed.insert(otherCharsOffset[i], otherChars[i]);
}
return reversed.toString();
}

private StringBuilder cleanSb;
private char[] otherChars;
private int poc;
private int[] otherCharsOffset;
private int poco;

private void washStr(String str) {
cleanSb = new StringBuilder();
int len = str.length();
otherChars = new char[len];
poc = 0;
otherCharsOffset = new int[len];
poco = 0;
for (int i = 0; i < len; i++) {
char c = str.charAt(i);
if (Character.isLetter(c)) {
cleanSb.append(c);
} else {
otherChars[poc++] = c;
otherCharsOffset[poco++] = i;
}
}
}
}