LC 2785.Sort Vowels in a String

题目描述

这是 LeetCode 上的 2785. 将字符串中的元音字母排序 ，难度为中等。

给你一个下标从 0 开始的字符串 s ，将 s 中的元素重新 排列 得到新的字符串 t ，它满足：

• 所有辅音字母都在原来的位置上。更正式的，如果满足 0 <= i < s.length 的下标 i 处的 s[i] 是个辅音字母，那么 t[i] = s[i] 。
• 元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的，对于满足 0 <= i < j < s.length 的下标 i 和 j ，如果 s[i] 和 s[j] 都是元音字母，那么 t[i] 的 ASCII 值不能大于 t[j] 的 ASCII 值。

请你返回结果字母串。

元音字母为 'a' ，'e' ，'i' ，'o' 和 'u' ，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。

示例 1：

输入：s = "lEetcOde"
输出："lEOtcede"
解释：'E' ，'O' 和 'e' 是 s 中的元音字母，'l' ，'t' ，'c' 和 'd' 是所有的辅音。将元音字母按照 ASCII 值排序，辅音字母留在原地。

示例 2：

输入：s = "lYmpH"
输出："lYmpH"
解释：s 中没有元音字母（s 中都为辅音字母），所以我们返回 "lYmpH" 。

提示：

• 1 <= s.length <= 10^5
• s 只包含英语字母表中的 大写 和 小写 字母。

解答

方法一：哈希表

A 的 ASCII 码值为65，而 u 的 ASCII 码值为117，于是创建哈希数组 hash 的长度为53，将字符串中可能出现的元音字母映射到数组 hash 上，顺便记住当前字符的位置 i ，然后就是遍历要插入的元音字符位置的动态数组 pos ，按照 ASCII 码值的顺序遍历 hash 数组，逐一将值添加到最终要返回的数组中。

class Solution {
    public String sortVowels(String s) {
        var pos = new LinkedList<Integer>();
        var cs = s.toCharArray();
        int[] hash = new int[53];
        for (int i = 0; i < cs.length; ++i) {
            if ("aeiouAEIOU".indexOf(cs[i]) >= 0) {
                ++hash[cs[i] - 65];
                pos.add(i);
            }
        }
        int j = 0;
        for (int i : pos) {
            while (hash[j] == 0) {
                ++j;
            }
            cs[i] = (char) (j + 65);
            --hash[j];
        }
        return new String(cs);
    }
}

• 时间复杂度：\(O(n)\)，其中 n 为字符串的长度，遍历字符串的时间复杂度为 \(O(n)\) ，而最坏情况下就是整个字符串都是元音字母，再次遍历插入位置数组的时间复杂度为\(O(n)\)，所以最终的时间复杂度为\(O(n)\)。

• 空间复杂度：\(O(n)\)，其中 n 为字符串的长度，存储插入位置的 LinkedList 最差情况存储整个字符串的每个位置，而 cs 存储一个字符串数组长度的字符， hash 和 j 的空间复杂度为 \(O(1)\)，所以最终的空间复杂度为\(O(n)\)。

每题一图