[LeetCode] 2785. Sort Vowels in a String

Given a 0-indexed string s, permute s to get a new string t such that:
All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].
Return the resulting string.

The vowels are ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’, and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

Example 1:
Input: s = “lEetcOde”
Output: “lEOtcede”
Explanation: ‘E’, ‘O’, and ‘e’ are the vowels in s; ‘l’, ‘t’, ‘c’, and ‘d’ are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

Example 2:
Input: s = “lYmpH”
Output: “lYmpH”
Explanation: There are no vowels in s (all characters in s are consonants), so we return “lYmpH”.

Constraints:
1 <= s.length <= 105
s consists only of letters of the English alphabet in uppercase and lowercase.

将字符串中的元音字母排序。

给你一个下标从 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 个字母以外的所有字母。

思路

思路就是排序，但是这道题我们只对元音字母排序。具体做法我们需要遍历 input 字符串两次。第一次遍历，我们可以用一个 list 把所有的元音字母记下来，然后对这个 list 按字典序排序，这样 list 中字典序较大的字母在前。第二次遍历，如果遇到的 index 原本是一个辅音字母，则直接加入 stringbuilder，如果遇到的 index 原本是元音字母，则去 list 中拿一个字母出来放到这个位置上。

复杂度

时间O(nlogn)
空间O(n)

代码

class Solution {
    public String sortVowels(String s) {
        int n = s.length();
        // 把元音字母的index记录下来
        List<Character> list = new ArrayList<>();
        String str = "aeiouAEIOU";
        for (int i = 0; i < n; i++) {
            char letter = s.charAt(i);
            if (str.indexOf(letter) != -1) {
                list.add(letter);
            }
        }

        Collections.sort(list, (a, b) -> a.compareTo(b));
        // System.out.println(list);
        int j = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            char letter = s.charAt(i);
            if (str.indexOf(letter) == -1) {
                sb.append(letter);
            } else {
                sb.append(list.get(j++));
            }
        }
        return sb.toString();
    }
}