熱門文章

2025年7月5日 星期六

ZeroJudge 解題筆記:a229. 括號匹配問題

作者:王一哲
日期:2025年7月5日


ZeroJudge 題目連結:a229. 括號匹配問題

解題想法


我用函式遞迴枚舉所有可能的組合,但是 Python 的部分一直超時,C++ 的部分用 string 儲存字串會超時,要用字元陣列才能過關。

Python 程式碼


寫法1,用字串儲存答案,超時。
import sys

def solve(n):
    """
    輸入括號對數 n,枚舉所有合法的組合
    """
    if n == 0: return [""]  # 特例,回傳只有空字串的串列
    result = []  # 儲存組合用的串列
    def backtrack(curr, left, right):
        """
        回溯,輸入現在的字串 curr、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合,加到 result
            result.append(f"{curr}\n")
            return
        if left < n:  # 如果左括號數量不夠,回溯,加上 (
            backtrack(curr+"(", left+1, right)
        if right < left:  # 如果右括號比左括號少,回溯,加上 )
            backtrack(curr+")", left, right+1)
    ### End of backtrack ###
    backtrack("", 0, 0)  # 呼叫 backtrack
    return result

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write("".join(solve(int(line))))

寫法2,因為用 + 連接字串比較慢,改用串列儲存字串內容,輸出前再組成字串,但還是超時。
import sys

def solve(n):
    """
    輸入括號對數 n,枚舉所有合法的組合
    """
    if n == 0:  # 特例,換行並 return
        sys.stdout.write("\n")
        return
    curr = [""]*(2*n+1)  # 儲存字串內容用的串列,事先分配好空間
    def backtrack(pos, left, right):
        """
        回溯,輸入正在處理的索引值 pos、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合,curr 接成字串並輸出
            sys.stdout.write("".join(curr[:pos]) + "\n")
            return
        if left < n:  # 如果左括號數量不夠,回溯,加上 (
            curr[pos] = "("
            backtrack(pos+1, left+1, right)
        if right < left:  # 如果右括號比左括號少,回溯,加上 )
            curr[pos] = ")"
            backtrack(pos+1, left, right+1)
    ### End of backtrack ###
    backtrack(0, 0, 0)  # 呼叫 backtrack

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    solve(int(line))


C++ 程式碼


寫法1,用 string 儲存字串內容,超時。
#include <iostream>
#include <string>
using namespace std;

void backtrack(string curr, int left, int right, int n) {
    /* 回溯,輸入現在的字串 curr、左括號數量 left、右括號數量 right、括號對數 n */
    if (left == n && right == n) {  // 找到新的組合,印出 curr 並 return
        cout << curr << "\n";
        return;
    }
    if (left < n) {  // 如果左括號數量不夠,回溯,加上 (
        backtrack(curr+"(", left+1, right, n);
    }
    if (right < left) {  // 如果右括號比左括號少,回溯,加上 )
        backtrack(curr+")", left, right+1, n);
    }
}

void solve(int n) {
    if (n == 0) return;  // 特例,直接 return
    string curr = "";  // 空字串
    backtrack(curr, 0, 0, n);  // 呼叫 backtrack
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, ca = 0;
    while(cin >> n) {
        ca++;
        if (ca > 1) cout << "\n";
        solve(n);
    }
    return 0;
}

寫法2,改用字元陣列儲存字串內容,使用時間約為 0.2 s,記憶體約為 288 kB,通過測試。
#include <iostream>
using namespace std;

void backtrack(char* curr, int pos, int left, int right, int n) {
    /* 回溯,輸入現在的字串 curr、索引值 pos、左括號數量 left、右括號數量 right、括號對數 n */
    if (left == n && right == n) {  // 找到新的組合,印出 curr 並 return
        curr[pos] = '\0';  // 加上字串結束符號
        cout << curr << "\n";
        return;
    }
    if (left < n) {  // 如果左括號數量不夠,回溯,加上 (
        curr[pos] = '(';
        backtrack(curr, pos+1, left+1, right, n);
    }
    if (right < left) {  // 如果右括號比左括號少,回溯,加上 )
        curr[pos] = ')';
        backtrack(curr, pos+1, left, right+1, n);
    }
}

void solve(int n) {
    if (n == 0) return;  // 特例,直接 return
    char* curr = new char[2*n + 1];  // 空字串,改用字元陣列
    backtrack(curr, 0, 0, 0, n);  // 呼叫 backtrack
    delete[] curr;  // 釋放記憶體
}

int main() {
    int n, ca = 0;
    while(cin >> n) {
        ca++;
        if (ca > 1) cout << "\n";
        solve(n);
    }
    return 0;
}


沒有留言:

張貼留言