3 min read leetcode

1249. Minimum Remove to Make Valid Parentheses

1249. Minimum Remove to Make Valid Parentheses
Photo by Markus Spiske / Unsplash

題目連結:​ Minimum Remove to Make Valid Parentheses

題目描述

給定一個字串 s，其包含英文字母和括號 (、)，請移除字串中最少數量的括號，使該字串中的所有括號排列都是「合法」的。

「合法」的定義如下：

  • 空字串為合法。
  • 若 A 與 B 為合法字串，則 AB（A 接 B）也是合法字串。
  • 若 A 為合法字串，則 (A) 也是合法字串。

簡言之，每個左括號 ( 都必須對應一個之後出現的右括號 )，整個字串中的括號匹配必須正確。

限制條件

  • 1 <= s.length <= 10^5
  • s[i] 為 '('、)' 或小寫英文字母

思考過程

此題的關鍵在於找出多餘的括號並移除。多餘的括號包括：

  1. 無法匹配的 )（右括號）：當前出現一個 )，卻沒有對應的左括號可供匹配時。
  2. 遍歷結束後，仍留在棧內未匹配到的 (（左括號）：表示這些 ( 沒有對應的 )。

藉由使用一個堆疊（stack）來追蹤左括號的位置，我們可以有效找出哪些括號需要被移除：

  1. 遍歷字串：
    • 遇到字母：直接跳過，不需處理。
    • 遇到左括號 (：將其索引壓入棧內。
    • 遇到右括號 )：
      • 若棧為空，表示無法匹配該右括號，將此索引記錄為需移除。
      • 若棧不為空，彈出棧頂（這對 ( 與 ) 已匹配成功）。
  2. 處理未匹配的 (：
    • 遍歷結束後，棧內若仍有未匹配的左括號索引，將這些索引記錄為需移除。
  3. 重建字串：
    • 將所有需要移除的索引記錄在資料結構中（如棧或雜湊表）。
    • 最後從頭到尾重建字串，跳過需移除的索引位置，即可得到合法字串。

下方程式碼為使用兩個堆疊分別記錄未匹配的左括號索引（st）與需移除的括號索引（shouldRemoved）的實作。

程式碼範例

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        const int n = s.size();
        stack<int> st;
        stack<int> shouldRemoved;

        for (int i = 0; i < n; i += 1) {
            if (s[i] == '(') {
                st.push(i);
            } else if (s[i] == ')') {
                if (st.empty()) {
                    shouldRemoved.push(i);
                } else {
                    st.pop();
                }
            }
        }

        if (st.empty() && shouldRemoved.empty()) {
            return s;
        }

        string ans = "";
        for (int i = n - 1; i >= 0; i -= 1) {
            if (!st.empty() && i == st.top()) {
                st.pop();
                continue;
            }
            if (!shouldRemoved.empty() && i == shouldRemoved.top()) {
                shouldRemoved.pop();
                continue;
            }
            ans += s[i];
        }
        return string(ans.rbegin(), ans.rend());
    }
};

時間與空間複雜度

  • 時間複雜度：O(N)
    • 遍歷字串需要 O(N) 時間。
    • 重建結果字串同樣為 O(N)。
    • 因此整體時間複雜度為 O(N)。
  • 空間複雜度：O(N)
    • 使用了 stack 與 unordered_set，最壞情況下可能需儲存所有的括號索引。
    • 因此空間複雜度為 O(N)。

最佳化方向

  • 可以使用原地（in-place）的方式降低空間佔用。例如：透過這種雙向掃描的方法，可在 O(N) 的時間下，僅使用 O(1) 的額外空間完成。這在 LeetCode 的討論中也有詳細範例可供參考。
    1. 先從左到右遍歷，移除多餘的右括號。
    2. 再從右到左遍歷，移除多餘的左括號。
  • 另外，也可使用 iterator 或其他方式減少拷貝次數，使程式在實務上執行速度更快。

Justin