345. 反轉字符串中的元音字母 - 力扣（LeetCode）
題目
給你一個字符串?s?，僅反轉字符串中的所有元音字母，并返回結果字符串。
元音字母包括?'a'、'e'、'i'、'o'、'u'，且可能以大小寫兩種形式出現不止一次。
示例 1：
輸入：s = "IceCreAm"
輸出："AceCreIm"
解釋：
s?中的元音是?['I', 'e', 'e', 'A']。反轉這些元音，s?變為?"AceCreIm".
示例 2：
輸入：s = "leetcode"
輸出："leotcede"
提示：
1 <= s.length <= 3 * 105s?由?可打印的 ASCII?字符組成
思路
- 兩種思路，一種是將找到的元音字母入棧，再重新遍歷遇到元音字母就彈棧修改；另一種是使用swap函數，利用首尾指針，將兩個元音直接交換。（速度快一點，少一遍遍歷）
代碼實現
class Solution {
public:string reverseVowels(string s) {int i = 0, n = s.length()-1;unordered_map<char, int> vocal= {{'a',1}, {'e',1}, {'i',1}, {'o',1}, {'u',1}, {'A',1}, {'E',1}, {'I',1}, {'O',1}, {'U',1}};while(i <= n) {if(vocal.count(s[i]) && vocal.count(s[n])) {swap(s[i], s[n]);i++;n--;}else if(vocal.count(s[i])) n--;else if(vocal.count(s[n])) i++;else {i++;n--;}}return s;}
};復雜度分析
- 時間復雜度：哈希查表的時間復雜度是O(1)的，經搜索swap在string和vector上的時間復雜度也是近似O(1)的，所以總的時間復雜度就是遍歷復雜度，最壞時間復雜度近似為O(n)。
- 空間復雜度：存了元音字符的哈希集合O(1)。
函數學習
- unordered_map的列表初始化方法unordered_map umap = {{key1,value1}, {key2, value2}};
- swap(a, b)——針對元素的交換時間是O(1)的，針對數組的交換時間是O(n)的，數組交換的過程中會導致迭代器失效，需注意。
)
