345.反转字符串中的元音字母

LeetCode LeetCode 字符串双指针

发布时间 : 2000-01-10 03:04

字数:1.1k 阅读 :

评论:

345.反转字符串中的元音字母

345.反转字符串中的元音字母

345.1 题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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 <= 10^5
s[i] 都是 ASCII 码表中的可打印字符

345.2 题解

方法一：双指针交换

思路

使用双指针从字符串两端向中间遍历。左指针找到元音字母后停止，右指针也找到元音字母后停止，然后交换两个元音字母。使用 HashSet 存储元音字母集合便于快速判断。

核心思想：首尾双指针找到元音字母后交换。

具体步骤：

定义元音字母集合 vowelsHashSet。
初始化双指针 left = 0, right = s.Length - 1。
当 left < right 时：
- left 向右移动直到找到元音字母
- right 向左移动直到找到元音字母
- 交换两个元音字母
返回结果字符串。

举例：对于 s = "hello"：

left=0, right=4：h 不是元音，left=1；o 是元音
left=1, right=4：e 是元音；交换 e 和 o，得到 "holle"
left=2, right=3：l 不是元音，left=3；l 不是元音，right=2
left >= right，结束
结果："holle"

复杂度分析

时间复杂度：O(n)，遍历一次字符串。
空间复杂度：O(1)，HashSet 大小固定为 10。

代码

// 方法一：双指针交换
// 用容器存储，双指针前后夹击找元音字母交换
static string ReverseVowels1(string s)
{
    // 将字符串转换为字符数组
    char[] charArray = s.ToCharArray();

    // 定义元音字母的集合
    HashSet<char> vowelsHashSet = new HashSet<char> { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };

    // 使用双指针交换元音字母位置
    int left = 0, right = charArray.Length - 1;
    while (left < right)
    {
        while (left < right && !vowelsHashSet.Contains(charArray[left]))
            left++;

        while (left < right && !vowelsHashSet.Contains(charArray[right]))
            right--;

        if (left < right)
        {
            // 交换元音字母位置
            char temp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = temp;
            left++;
            right--;
        }
    }

    // 将字符数组转换为字符串并返回
    return new string(charArray);
}

345.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
        // 元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。
        // 示例 1：
        // 输入：s = "hello"
        // 输出："holle"
        // 示例 2：
        // 输入：s = "leetcode"
        // 输出："leotcede"
        // 提示：
        // 1 <= s.length <= 3 * 105
        // s 由 可打印的 ASCII 字符组成

        #endregion

        #region 测试

        // 示例 1
        string str1 = "hello";
        string result1_1 = ReverseVowels1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");

        // 示例 2
        string str2 = "leetcode";
        string result2_1 = ReverseVowels1(str2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");

        #endregion
    }

    #region 答案

    // 方法一：双指针交换
    // 用容器存储，双指针前后夹击找元音字母交换
    static string ReverseVowels1(string s)
    {
        // 将字符串转换为字符数组
        char[] charArray = s.ToCharArray();

        // 定义元音字母的集合
        HashSet<char> vowelsHashSet = new HashSet<char> { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };

        // 使用双指针交换元音字母位置
        int left = 0, right = charArray.Length - 1;
        while (left < right)
        {
            while (left < right && !vowelsHashSet.Contains(charArray[left]))
                left++;

            while (left < right && !vowelsHashSet.Contains(charArray[right]))
                right--;

            if (left < right)
            {
                // 交换元音字母位置
                char temp = charArray[left];
                charArray[left] = charArray[right];
                charArray[right] = temp;
                left++;
                right--;
            }
        }

        // 将字符数组转换为字符串并返回
        return new string(charArray);
    }

    #endregion
}

345.4 运行结果

示例1 方法1 输出：holle
示例2 方法1 输出：leotcede

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com