LeetCode 解題筆記：1807. Evaluate the Bracket Pairs of a String

作者：王一哲
日期：2026年9月26日


LeetCode 題目連結：1807. Evaluate the Bracket Pairs of a String

解題想法

中等難度題，如果會使用 Python dict 或是 C++ map、unordered_map 物件，這題算相對簡單。題目給一個字串 $s$，$s$ 之中只有小寫英文字母及 (、)，括號一定成對，而且沒有巢狀結構，也就是左、右括號之間不會有其它的括號，這樣程式碼會很好寫。再給一個二維陣列 $knowledge$，每一組有兩個字串 $key, value$。檢查 $s$ 的內容，將一組括號之間的子字串 $sub$ 替換成 $knowledge$ 之中對應的字串，如果沒有對應的字串則替換成 ?。回傳替換後的字串。

首先為了便於查詢 $knowledge$ 之中 $key$ 對應的 $value$，建立一個字典物件 $words$，儲存 $key: value$。用變數 $pre$ 記錄目前已找到的左括號索引值，$-1$ 代表目前沒有左括號。替換後的答案存到 $res$。用一個 for 迴圈掃過字串 $s$，假設字元 $c = s[i]$，接下來有 3 種狀況：

1. 如果 $c$ 是左括號，更新 $pre = i$。
2. 如果 $c$ 是右括號，切下子字串 $sub = s[pre + 1 : i]$。如果 $sub$ 不在 $words$ 之中，將 ? 加入 $res$。如果 $sub$ 在 $words$ 之中，將對應的字串加入 $res$。
3. 如果 $c$ 是字母，而且 $pre = -1$，將 $c$ 加入 $res$。

如果不想用 Python 的字串切片或是 C++ 的 substr，也可以修改以上第3種狀況的處理方式，如果 $c$ 是字母，再分成 $pre = -1$ 的將況，將 $c$ 加入 $res$；$pre \neq -1$，$c$ 加入 $sub$。同時要修改第2種狀況，結算完 $sub$ 之後要重設 $sub$，才能正確地處理下一個子字串。

Python 程式碼

Runtime: 47 ms, beats 69.16%. Memory: 51.39 MB, beats 81.62%.

class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        words = {key: val for key, val in knowledge}  # knowledge 轉成字典
        n = len(s)  # 長度
        pre = -1  # 目前找到的 ( 索引值
        res = []  # 答案

        # 依序讀取 s 的字元
        for i in range(n):
            c = s[i]
            if c == '(':  # 找到 (，記錄索引值
                pre = i
            elif c == ')':  # 找到 )
                sub = s[pre + 1 : i]  # 切下 () 之間的子字串
                if sub not in words:  # sub 不在 words 之中，加上 ?
                    res.append("?")
                else:  # sub 在 words 之中，加上對應的值
                    res.append(words[sub])
                pre = -1  # 重設為 -1
            elif pre == -1:  # 找到字母而且目前沒有 (，直接將字母加到 res
                res.append(c)
        
        return "".join(res)  # 接成字串再回傳

用 get 從 $words$ 之中取 $sub$ 對應的字串，如果 $sub$ 不在 $words$ 之中則回傳指定的預設值 ?，這樣寫起來更方便。Runtime: 47 ms, beats 69.16%. Memory: 51.29 MB, beats 97.82%.

class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        words = {key: val for key, val in knowledge}  # knowledge 轉成字典
        n = len(s)  # 長度
        pre = -1  # 目前找到的 ( 索引值
        res = []  # 答案

        # 依序讀取 s 的字元
        for i in range(n):
            c = s[i]
            if c == '(':  # 找到 (，記錄索引值
                pre = i
            elif c == ')':  # 找到 )
                sub = s[pre + 1 : i]  # 切下 () 之間的子字串
                # 用 get 從 words 之中取 sub 對應的值，如果沒有值回傳 ?
                res.append(words.get(sub, "?"))
                pre = -1  # 重設為 -1
            elif pre == -1:  # 找到字母而且目前沒有 (，直接將字母加到 res
                res.append(c)
        
        return "".join(res)  # 接成字串再回傳

不使用字串切片，需要用 + 串接字串，速度較慢。Runtime: 51 ms, beats 57.94%. Memory: 51.33 MB, beats 81.62%.

class Solution:
    def evaluate(self, s: str, knowledge: list[list[str]]) -> str:
        words = {key: val for key, val in knowledge}  # knowledge 轉成字典
        n = len(s)  # 長度
        pre = -1  # 目前找到的 ( 索引值
        res = []  # 答案
        sub = ""  # () 之間的子字串

        # 依序讀取 s 的字元
        for i in range(n):
            c = s[i]
            if c == '(':  # 找到 (，記錄索引值
                pre = i
            elif c == ')':  # 找到 )，結算 sub
                # 用 get 從 words 之中取 sub 對應的值，如果沒有值回傳 ?
                res.append(words.get(sub, "?"))
                sub = ""  # 重設 sub
                pre = -1  # 重設為 -1
            else:  # 找到字母
                if pre == -1:  # 目前沒有 (，直接將字母加到 res
                    res.append(c)
                else:  # 目前有 (，字母加到 sub
                    sub += c
        
        return "".join(res)  # 接成字串再回傳

C++ 程式碼

Runtime: 111 ms, beats 34.58%. Memory: 144.67 MB, beats 20.56%.

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        // knowledge 轉成字典
        unordered_map<string, string> words;
        for(auto it : knowledge) {
            words[it[0]] = it[1];
        }
        // 長度，目前找到的 ( 索引值
        int n = (int)s.size(), pre = -1;
        // 答案，直接用字串格式
        string res;

        // 依序讀取 s 的字元
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if (c == '(') {  // 找到 (，記錄索引值
                pre = i;
            } else if (c == ')') {  // 找到 )
                string sub = s.substr(pre + 1, i - pre - 1);  // 切下 () 之間的子字串
                if (words.count(sub) == 0) {  // sub 不在 words 之中，加上 ?
                    res += "?";
                } else {  // 反之，加上 sub 對應的值
                    res += words[sub];
                }
                pre = -1;  // 重設為 -1
            } else if (pre == -1) {  // 找到字母而且目前沒有 (，直接將字母加到 res
                res += c;
            }
        }
        return res;
    }
};

不使用 substr，速度較慢。Runtime: 114 ms, beats 32.09%. Memory: 144.74 MB, beats 13.71%.

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        // knowledge 轉成字典
        unordered_map<string, string> words;
        for(auto it : knowledge) {
            words[it[0]] = it[1];
        }
        // 長度，目前找到的 ( 索引值
        int n = (int)s.size(), pre = -1;
        // 答案、() 之間的子字串，直接用字串格式
        string res, sub;

        // 依序讀取 s 的字元
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if (c == '(') {  // 找到 (，記錄索引值
                pre = i;
            } else if (c == ')') {  // 找到 )，結算 sub
                if (words.count(sub) == 0) {  // sub 不在 words 之中，加上 ?
                    res += "?";
                } else {  // 反之，加上 sub 對應的值
                    res += words[sub];
                }
                sub.clear();  // 重設 sub
                pre = -1;  // 重設為 -1
            } else {  // 找到字母
                if (pre == -1) {  // 目前沒有 (，直接將字母加到 res
                    res += c;
                } else {  // 目前有 (，字母加到 sub
                    sub += c;
                }
            }
        }
        return res;
    }
};