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();
}
}
- LeetCode Vowels String 2785 Sortleetcode vowels string 2785 leetcode people 2418 sort comparator leetcode arrays sort characters leetcode string extra leetcode largest number string 2785 leetcode removing string stars difference leetcode string 2451 leetcode pieces obtain string partition leetcode optimal string