Medium

题目描述

给定一个下标从 0 开始的字符串 s，重新排列 s 中的字符得到新字符串 t，使得：

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

返回结果字符串。

元音字母是 ‘a’、’e’、‘i’、‘o’ 和 ‘u’，它们可以是小写或大写形式。辅音字母是所有不是元音字母的字母。

示例 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 只包含英文字母的大写和小写形式

解题思路

这道题要求我们对字符串中的元音字母按ASCII值排序，同时保持辅音字母的原始位置不变。

解题思路：

  1. 提取元音字母：遍历字符串，找出所有元音字母（包括大小写的a、e、i、o、u）
  2. 排序元音字母：将提取的元音字母按ASCII值从小到大排序
  3. 重构字符串：再次遍历原字符串，遇到辅音字母直接保留，遇到元音字母则按顺序替换为排序后的元音字母

算法步骤：

  • 首先定义一个函数来判断字符是否为元音字母
  • 遍历字符串收集所有元音字母到数组中
  • 对元音字母数组进行排序
  • 使用双指针技巧，重新遍历原字符串，用排序后的元音字母逐个替换原来的元音字母位置

这种方法时间复杂度主要取决于排序操作和两次遍历，空间复杂度取决于元音字母的数量。

代码实现

class Solution {
public:
    string sortVowels(string s) {
        auto isVowel = [](char c) {
            return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
                   c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
        };
        
        vector<char> vowels;
        for (char c : s) {
            if (isVowel(c)) {
                vowels.push_back(c);
            }
        }
        
        sort(vowels.begin(), vowels.end());
        
        int vowelIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s[i])) {
                s[i] = vowels[vowelIndex++];
            }
        }
        
        return s;
    }
};

class Solution:
    def sortVowels(self, s: str) -> str:
        def is_vowel(c):
            return c in 'aeiouAEIOU'
        
        vowels = [c for c in s if is_vowel(c)]
        vowels.sort()
        
        result = []
        vowel_index = 0
        
        for c in s:
            if is_vowel(c):
                result.append(vowels[vowel_index])
                vowel_index += 1
            else:
                result.append(c)
        
        return ''.join(result)

public class Solution {
    public string SortVowels(string s) {
        bool IsVowel(char c) {
            return "aeiouAEIOU".Contains(c);
        }
        
        var vowels = new List<char>();
        foreach (char c in s) {
            if (IsVowel(c)) {
                vowels.Add(c);
            }
        }
        
        vowels.Sort();
        
        var result = new char[s.Length];
        int vowelIndex = 0;
        
        for (int i = 0; i < s.Length; i++) {
            if (IsVowel(s[i])) {
                result[i] = vowels[vowelIndex++];
            } else {
                result[i] = s[i];
            }
        }
        
        return new string(result);
    }
}

var sortVowels = function(s) {
    const isVowel = (c) => 'aeiouAEIOU'.includes(c);
    
    const vowels = [];
    for (const c of s) {
        if (isVowel(c)) {
            vowels.push(c);
        }
    }
    
    vowels.sort();
    
    const result = [];
    let vowelIndex = 0;
    
    for (const c of s) {
        if (isVowel(c)) {
            result.push(vowels[vowelIndex++]);
        } else {
            result.push(c);
        }
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log k)，其中 n 是字符串长度，k 是元音字母数量。需要遍历字符串两次 O(n)，排序元音字母 O(k log k)
空间复杂度O(k)，其中 k 是元音字母数量，用于存储提取的元音字母数组

相关题目