leetcode
leetcode 801 ~ 850
仅仅反转字母

仅仅反转字母

难度:

标签:

题目描述

代码结果

运行时间: 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'),这种情况下算法的效率如何?是否有冗余操作?
即使左右指针指向相同的字母,如'aa',交换操作仍会进行,但这并不会影响算法的总体效率。虽然这看起来是冗余的操作,因为交换相同的字符并不会改变字符串的状态,但这种情况的处理并不会引入额外的时间复杂度,因为每次操作仍然是常数时间内完成。因此,尽管存在这种看似冗余的操作,它并不会显著影响算法的效率。
🦆
题解中提到当左右指针都指向字母时才进行交换,这样的处理方式能否保证所有的英文字母都被正确反转,即使它们被非字母字符隔开?
是的,这种处理方式确实可以保证所有的英文字母都被正确反转。算法通过移动两个指针,跳过非字母字符,只有当两个指针都指向字母时才进行交换。这确保了即使字母被非字母字符隔开,它们仍然会与字符串中相对应位置的字母交换位置。因此,无论字母之间的间隔如何,所有的字母最终都会被反转到正确的位置。

相关问题