leetcode
leetcode 301 ~ 350
反转字符串中的元音字母

反转字符串中的元音字母

难度:

标签:

题目描述

给你一个字符串 s ,仅反转字符串中的所有元音字母,并返回结果字符串。

元音字母包括 'a''e''i''o''u',且可能以大小写两种形式出现不止一次。

 

示例 1:

输入:s = "hello"
输出:"holle"

示例 2:

输入:s = "leetcode"
输出:"leotcede"

 

提示:

  • 1 <= s.length <= 3 * 105
  • s可打印的 ASCII 字符组成

代码结果

运行时间: 30 ms, 内存: 16.9 MB


/*
 * 思路:
 * 1. 使用双指针法,一个指针从字符串的开头开始,另一个指针从字符串的结尾开始。
 * 2. 当两个指针都指向元音字母时,交换这两个元音字母。
 * 3. 移动指针继续检查,直到两个指针相遇。
 * 4. 使用Java Stream来处理字符数组。
 */
 
import java.util.*;
import java.util.stream.*;
 
public class Solution {
    public String reverseVowels(String s) {
        if (s == null || s.length() == 0) return s;
        List<Character> vowels = Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U');
        List<Character> vowelsInS = s.chars()
                                      .mapToObj(c -> (char) c)
                                      .filter(vowels::contains)
                                      .collect(Collectors.toList());
        Collections.reverse(vowelsInS);
        Iterator<Character> iterator = vowelsInS.iterator();
        return s.chars()
                .mapToObj(c -> vowels.contains((char) c) ? iterator.next() : (char) c)
                .map(String::valueOf)
                .collect(Collectors.joining());
    }
}

解释

方法:

本题解使用双指针的方法来解决反转字符串中元音字母的问题。具体思路如下: 1. 定义一个哈希表 table 存储所有元音字母,方便后续判断字符是否为元音字母。 2. 定义双指针 left 和 right,分别指向字符串的开头和结尾。 3. 将字符串转换为列表 ss,方便修改字符。 4. 当 left 小于 right 时,进入循环: - 如果 ss[left] 和 ss[right] 都是元音字母,则交换两个字符,并将 left 右移、right 左移。 - 如果 ss[left] 是元音字母而 ss[right] 不是,则 right 左移。 - 如果 ss[left] 不是元音字母而 ss[right] 是,则 left 右移。 - 如果 ss[left] 和 ss[right] 都不是元音字母,则 left 右移、right 左移。 5. 循环结束后,将列表 ss 重新拼接为字符串并返回结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择将字符串转换为列表来进行字符交换,直接修改字符串不可以吗?
在Python中,字符串是不可变的数据类型,这意味着一旦创建了字符串,就不能修改其中的单个字符。要进行字符交换,我们需要将字符串转换成可变的数据类型,如列表。在列表中完成所有必要的修改后,可以将列表转换回字符串来得到最终结果。这种方法比创建多个字符串副本更为高效,尤其是在需要多次修改字符串时。
🦆
在判断字符是否为元音时,使用哈希表与直接使用字符串比较有什么优势?
使用哈希表(在Python中实现为集合)来存储和查找元音字母具有更高的效率。在哈希表中,查找操作的平均时间复杂度为O(1),而在字符串中查找字符的时间复杂度为O(n),其中n是字符串的长度。这意味着使用哈希表可以更快地判断一个字符是否为元音,特别是在字符集较大或查找操作非常频繁的情况下。
🦆
哈希表中包含元音字母的大写和小写形式,这是否意味着算法对大小写敏感?
哈希表中同时包含元音字母的大写和小写形式说明算法是大小写不敏感的,即它可以正确识别并处理大写和小写的元音字母。包括两种形式是为了确保算法能够在不区分大小写的情况下工作,反转所有的元音字母,无论它们出现在字符串中的位置或形式如何。
🦆
在结束循环的条件是`left < right`,这样的条件是否能确保所有元音字母都被考虑到了?还是可能有遗漏?
循环条件`left < right`确保了只要左指针位于右指针的左侧,循环就会继续执行。这样的条件通常足以确保所有元音字母都被考虑到,因为算法会从两端向中间遍历字符串。当两个指针相遇时,意味着字符串的所有部分都已经被考虑过,不会遗漏任何元音字母。此外,如果字符串中间的字符是元音,它在指针相遇时也会被检查。因此,这一条件通常不会导致遗漏。

相关问题

反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

 

示例 1:

输入:s = ["h","e","l","l","o"]
输出:["o","l","l","e","h"]

示例 2:

输入:s = ["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]

 

提示:

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符

删去字符串中的元音

删去字符串中的元音