当前位置：首页 > 文章列表 > 文章 > 前端 > Typescript 编码编年史：字符串的反转元音

Typescript 编码编年史：字符串的反转元音

来源：dev.to 2024-07-11 12:15:49 0浏览收藏

欢迎各位小伙伴来到golang学习网，相聚于此都是缘哈哈哈！今天我给大家带来《Typescript 编码编年史：字符串的反转元音》，这篇文章主要讲到等等知识，如果你对文章相关的知识非常感兴趣或者正在自学，都可以关注我，我会持续更新相关文章！当然，有什么建议也欢迎在评论留言提出！一起学习！

问题陈述：

给定一个字符串 s，仅反转字符串中的所有元音并返回它。

元音是 'a'、'e'、'i'、'o' 和 'u'，它们可以以小写和大写形式出现多次。

示例1：

输入：s =“你好”
输出：“holle”

示例2：

输入：s = "leetcode"
输出：“leotcede”

限制条件：

1 <= s.length <= 3 * 10^5
s 由可打印的 ascii 字符组成。

初步思考过程：

为了解决这个问题，我们需要识别字符串中的所有元音，颠倒它们的顺序，然后将它们放回原来的位置。这可以使用两种方法来完成：

蛮力方法：提取元音，反转它们，然后在字符串中替换它们。
双指针方法：使用两个指针来反转元音。

基本解决方案：

代码：

function reversevowelsbruteforce(s: string): string {
    const vowels = new set(['a', 'e', 'i', 'o', 'u', 'a', 'e', 'i', 'o', 'u']);
    let vowellist: string[] = [];

    // extract vowels from the string
    for (let char of s) {
        if (vowels.has(char)) {
            vowellist.push(char);
        }
    }

    // reverse the list of vowels
    vowellist.reverse();

    // create a result array to build the output string
    let result: string[] = [];
    let vowelindex = 0;

    // reconstruct the string with reversed vowels
    for (let char of s) {
        if (vowels.has(char)) {
            result.push(vowellist[vowelindex]);
            vowelindex++;
        } else {
            result.push(char);
        }
    }

    return result.join('');
}

时间复杂度分析：

时间复杂度： o(n)，其中n是字符串的长度。提取元音、反转元音以及重建字符串都需要 o(n) 时间。
空间复杂度： o(n)，用于存储元音和结果数组。

限制：

暴力解决方案效果很好，但使用额外的空间来存储元音和结果数组。

优化方案：

代码：

function reversevowelsoptimized(s: string): string {
    const vowels = new set(['a', 'e', 'i', 'o', 'u', 'a', 'e', 'i', 'o', 'u']);
    let sarray = s.split('');
    let left = 0;
    let right = sarray.length - 1;

    while (left < right) {
        while (left < right && !vowels.has(sarray[left])) {
            left++;
        }
        while (left < right && !vowels.has(sarray[right])) {
            right--;
        }

        if (left < right) {
            [sarray[left], sarray[right]] = [sarray[right], sarray[left]];
            left++;
            right--;
        }
    }

    return sarray.join('');
}

时间复杂度分析：

时间复杂度： o(n)，其中n是字符串的长度。每个字符最多检查两次。
空间复杂度： o(n)，用于字符串的数组表示。如果我们不计算输入和输出字符串所使用的空间，则空间复杂度可以认为是 o(1)。

基本解决方案的改进：

优化的解决方案使用两指针方法将元音反转到位，减少对额外空间的需求。

边缘情况和测试：

边缘情况：

该字符串不包含元音。
该字符串仅包含元音。
该字符串有大写和小写元音。
字符串长度达到最小或最大限制。

测试用例：

console.log(reverseVowelsBruteForce("hello")); // "holle"
console.log(reverseVowelsBruteForce("leetcode")); // "leotcede"
console.log(reverseVowelsBruteForce("aA")); // "Aa"
console.log(reverseVowelsBruteForce("")); // ""
console.log(reverseVowelsBruteForce("bcdfg")); // "bcdfg"

console.log(reverseVowelsOptimized("hello")); // "holle"
console.log(reverseVowelsOptimized("leetcode")); // "leotcede"
console.log(reverseVowelsOptimized("aA")); // "Aa"
console.log(reverseVowelsOptimized("")); // ""
console.log(reverseVowelsOptimized("bcdfg")); // "bcdfg"