【leetcode解題日記】151. 反轉字串中的單詞 (中等)

今天來分享一個中等難度的 LeetCode 題目 —— 反轉字串中的單詞。如果只是要反轉字串中的單詞及移除空格，可以透過split()、reverse()、trim()等方法即可達成，這樣此題可能有負其中等之名。因此，題目有進階的要求，即空間複雜度要是O(1)，因此無法使用額外的空間來儲存split() 創建的數組以及最終結果。

題目說明

給你一個字串 s，請你反轉字串中 單詞 的順序。

單詞 是由非空格字元組成的字串。s中使用至少一個空格將字串中的 單詞 分隔開。

返回 單詞 順序顛倒且 單詞 之間用單個空格連接的結果字串。

注意：輸入字串s中可能會存在前導空格、尾隨空格或者單詞間的多個空格。返回的結果字串中，單詞間應當僅用單個空格分隔，且不包含任何額外的空格。

進階：如果字串在你使用的程式設計語言中是一種可變資料類型，請嘗試使用 O(1) 額外空間複雜度的 原地 解法。

解題思路

由於無法使用額外空間，我們可以透過三個步驟來對同一個陣列進行處理，即可達成 O(1) 空間複雜度的解答。

1. 移除多餘空格("the sky is blue")
2. 反轉字串("eulb si yks eht")
3. 反轉各單詞("blue is sky the")

var reverseWords = function(s) {
    // 字串轉陣列
    const strArr = Array.from(s);
    // 移除多餘空格
    removeExtraSpace(strArr);
    // 反轉
    reverse(strArr, 0, strArr.length - 1)

    let start = 0;

    for(let i = 0; i <= strArr.length; i++){
        if(strArr[i] === ' ' || i === strArr.length){
            // 反轉各單詞
            reverse(strArr, start, i - 1);
            start = i + 1
        }
    }

    return strArr.join('')
};

// 刪除多餘空格
function removeExtraSpace(strArr){
    // 雙指針
    // 用於寫入有效字元(移除多於空格後的結果)
    let slowIndex = 0;
    // 用於掃描整個陣列
    let fastIndex = 0;

    while(fastIndex < strArr.length){
        // 移除開始位置的控制和重複的空格
        if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')){
            fastIndex++;
        } else {
            // 原地覆寫字元陣列
            strArr[slowIndex++] = strArr[fastIndex++]
        }
    }

    // 移除末尾的空格
    strArr.length = strArr[slowIndex - 1 ] === ' ' ? slowIndex - 1 : slowIndex
}

// 反轉從 start 到 end 的字串
function reverse(strArr, start, end){
    let left = start;
    let right = end;

    while(left < right){
        // 交換
        [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
        left++;
        right--;
    }
}

關鍵變數

• strArr：將字串 s 拆解為陣列，進行原地操作（移除空格、反轉等）
• fastIndex：快指標，用於掃描原陣列中所有字元
• slowIndex：慢指標，用於覆寫有效字元、建立最終結果
• start：單詞的起始位置，用於標記每個單詞的開始以利反轉
• left、right：雙指針，用於在 reverse 函式中交換字元達到反轉效果

總結

這題的核心在於使用 原地操作（in-place）來避免額外空間浪費，透過三個步驟完成：

1. 移除多餘空格： 透過雙指針方法的fastIndex來標記出有效的字元，並透過slowIndex來記錄有效字元要放入的位置，並透過strArr[slowIndex++] = strArr[fastIndex++]來達成單詞陣列的原地覆寫，即可移除陣列中多餘的空格
2. 整體反轉字串： 透過雙指針方法，透過設定reverse(strArr, start, end)函式，將整個字串陣列反轉
3. 逐個單詞反轉： 透過辨識空格切割每個單詞，針對每個單詞再分別反轉回正確順序。

此方法不僅可以維持 O(1) 的額外空間複雜度，也很適合拿來練習雙指針方法與字元操作。

另外，時間複雜度為O(n)，且空間複雜度為O(n)的解法如下： 

var reverseWords = function(s) {
    let ans = "";
    for(let item of s.split(' ').reverse()) {
        if(item.trim() != '') {
            ans += item.trim();
            ans += ' ';
        }
    }
    return ans.trim()
};