[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 概念複習：

演算法筆記系列 — Two Pointer 與Sliding Window

• 一樣需要存一個母音的表
• 同時從頭尾往中間移動，兩邊都遇到母音就直接交換位置

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 為固定常數長度

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記