[LeetCode 解題紀錄] 345. Reverse Vowels of a String
345. Reverse Vowels of a String
https://leetcode.com/problems/reverse-vowels-of-a-string/
Problem:
Given a string s
, reverse only all the vowels in the string and return it.
The vowels are 'a'
, 'e'
, 'i'
, 'o'
, and 'u'
, and they can appear in both lower and upper cases, more than once.
Example 1:
Input: s = "hello"
Output: "holle"
Example 2:
Input: s = "leetcode"
Output: "leotcede"
Constraints:
1 <= s.length <= 3 * 105
s
consist of printable ASCII characters.
題意
這題的題意很明確,反轉字串 s 當中母音的位置,母音有分大小寫且可以重複出現,要將他們的位置前後對調。直接看例子會是最清楚的:
- 輸入:hello
- 輸出:holle
問題解析:
遇到判斷母音,或是判斷某些特定的值的時候,通常會需要存一個表,透過查表來做判斷,而我們通常都會使用一個簡單陣列,然後使用 indexOf
來做查表,這是最簡單直覺的方式。
然而,其實在執行 indexOf
或是 includes
這類原生方法的時候,最差的時間複雜度其實會是 O(n)
,因此可以考慮這種情況下,改成用 Hash Map 的方式來做這張表,讓查表的時間直接縮減為 O(1)
,實作上透過使用 Set
或是 Map
的資料結構。
解法
暴力法
這題因為不算太複雜,且暴力解的時間複雜度也不會到太差,可以先從暴力解來試試看。
直觀的想法:
- 遍歷整個字串,找到所有的母音字母,並將它們存儲在一個陣列中。
- 再次遍歷整個字串,當遇到母音字母時,從存儲母音字母的陣列中取出最後一個母音字母,替換當前的母音字母。
var reverseVowels = function(s) {
const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
const chars = s.split('');
const collectedVowels = [];
for (let char of chars) {
if (vowels.has(char)) {
collectedVowels.push(char);
}
}
for (let i = 0; i < chars.length; i++) {
if (vowels.has(chars[i])) {
chars[i] = collectedVowels.pop();
}
}
return chars.join('');
};
- 時間複雜度:
O(n)
- 空間複雜度:
O(n)
可以提一下的部分,在解題中用到的「從存儲母音字母的陣列中取出最後一個母音字母」,這裡的 collectedVowels
這個陣列,其實是使用到了 Stack 的觀念 FILO,透過 array 的 pop()
來實現。
Two Pointers
這題其實暴力法(stack 方法)的效率已經不錯了,我自己是沒想出還有什麼更高效的方法,因為至少都必須要遍歷整個字串一次。不過在解題的時候也可以思考,那還有什麼不同方法可以來使用?
針對這題的話,我們可以降低他的空間複雜度,使用 two pointers 的方法來解決,就可以不預先把字串有的母音存下來,節省空間。
Sliding Window / Two Pointers 概念複習:
- 一樣需要存一個母音的表
- 同時從頭尾往中間移動,兩邊都遇到母音就直接交換位置
var reverseVowels = function(s) {
const len = s.length;
if (len <= 1) return s;
const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
let left = 0;
let right = len - 1;
while (left < right) {
while (left < right && !vowels.has(s[left])) {
left++;
}
while (left < right && !vowels.has(s[right])) {
right--;
}
if (left < right) {
[s[left], s[right]] = [s[right], s[left]];
left++;
right--;
}
}
return s;
};
- 時間複雜度:
O(n)
- 空間複雜度:
O(1)
, Set 為固定常數長度