仅仅反转字母
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 16.0 MB
/*
* 思路:
* 1. 使用Stream将字符串中的所有英文字母收集到一个栈中。
* 2. 使用StringBuilder遍历原始字符串,遇到英文字母时从栈中弹出一个字符,并将其追加到StringBuilder中。
* 3. 非英文字母则直接追加到StringBuilder中。
* 4. 最终返回StringBuilder的字符串表示。
*/
import java.util.Stack;
import java.util.stream.Collectors;
public class Solution {
public String reverseOnlyLetters(String s) {
Stack<Character> letters = s.chars()
.filter(Character::isLetter)
.mapToObj(c -> (char) c)
.collect(Collectors.toCollection(Stack::new));
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetter(c)) {
result.append(letters.pop());
} else {
result.append(c);
}
}
return result.toString();
}
}
解释
方法:
题解采用双指针技术,分别从字符串的首尾开始遍历。左指针left从前向后移动,右指针right从后向前移动。如果左指针指向的字符不是字母,则将该字符直接复制到结果中并移动左指针。如果右指针指向的字符不是字母,则将该字符直接复制到结果中并移动右指针。当左右指针均指向字母时,将它们的位置互换,即将右指针的字母放到左指针的位置,左指针的字母放到右指针的位置,然后同时移动两个指针。这个过程一直进行,直到left大于right为止。最后,将结果数组转换为字符串形式返回。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么选择使用双指针方法来解决这个问题,单指针或者其他方法是否可行?
▷🦆
在处理字符交换时,如果左右指针都指向相同的字母(如'aa'),这种情况下算法的效率如何?是否有冗余操作?
▷🦆
题解中提到当左右指针都指向字母时才进行交换,这样的处理方式能否保证所有的英文字母都被正确反转,即使它们被非字母字符隔开?
▷