这是悦乐书的第353次更新，第378篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第215题（顺位题号是917）。给定一个字符串S，返回“反向”字符串，其中所有非字母的字符都保留在同一位置，并且所有字母都反转其位置。例如：
输入：“ab-cd”
输出：“dc-ba”
输入：“a-bC-dEf-ghIj”
输出：“j-Ih-gfE-dCba”
输入：“Test1ng-Leet = code-Q！”
输出：“Qedo1ct-eeLg = ntse-T！”
注意：
S.length <= 100
33 <= S[i].ASCIIcode <= 122
S不包含
\或“
02 第一种解法
使用双指针。
定义两个指针i和j，一个从前往后，一个从后往前，只有两个指针所在元素都是字母时才交换位置，如果其中一个不是字母，就向前前进一步继续判断，如果两个指针所在元素都不是字母就同时向前移动。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public String reverseOnlyLetters(String S) {
int i = 0, j = S.length()-1;
char[] arr = S.toCharArray();
while (i < j) {
char c = arr[i];
char c2 = arr[j];
if (Character.isLetter(c) && Character.isLetter(c2)) {
arr[i] = c2;
arr[j] = c;
i++;
j--;
} else if (!Character.isLetter(c) && Character.isLetter(c2)) {
i++;
} else if (Character.isLetter(c) && !Character.isLetter(c2)) {
j--;
} else if (!Character.isLetter(c) && !Character.isLetter(c2)) {
i++;
j--;
}
}
return new String(arr);
}
03 第二种解法
在双指针的基础上做了下变动，使用StringBuilder来拼接新的字符，但是双指针的思路没变。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public String reverseOnlyLetters2(String S) {
int j = S.length()-1, n = S.length();
StringBuilder sb = new StringBuilder();
for (int i=0; i<n; i++) {
if (Character.isLetter(S.charAt(i))) {
while (j>=0 && !Character.isLetter(S.charAt(j))) {
j--;
}
sb.append(S.charAt(j--));
} else {
sb.append(S.charAt(i));
}
}
return sb.toString();
}
04 第三种解法
利用栈，借助其先进后出的特性。
先将S中的字母全部入栈，然后再遍历S中的字符，如果是字母，就从栈顶取一位元素出来拼接，不是字母，就直接拼接当前元素。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public String reverseOnlyLetters3(String S) {
Stack<Character> stack = new Stack<Character>();
char[] arr = S.toCharArray();
for (char c : arr) {
if (Character.isLetter(c)) {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
for (char c : arr) {
if (Character.isLetter(c)) {
sb.append(stack.pop());
} else {
sb.append(c);
}
}
return sb.toString();
}
05 小结
算法专题目前已连续日更超过六个月，算法题文章221+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
