PHP實現反轉括號內子字符串的高效方法

字符串處理中的常見問題

在編程過程中，字符串的處理是非常頻繁的需求。特別是在遇到括號及其嵌套結構時，反轉括號內的子字符串常常讓開發者感到棘手。本文將從問題描述、算法思路到具體實現，系統介紹如何反轉每對括號內的字符串。

問題描述

給定一個包含普通字符和括號的字符串，目標是將每對括號之間的內容反轉。例如，輸入"(abc)de(fgh)"，期望輸出為"cbadehgf"。通過明晰的規則和步驟，能夠有效解決此類問題。

輸入輸出示例

以下示例有助於理解問題：

 輸入: "(xyz)(abc)"
輸出: "zyxcba"

輸入: "a(bc(de)fg)h"
輸出: "ahgfedcba"

實現思路

解決此問題最合適的數據結構是棧，因為棧可以方便地管理括號的嵌套層級。整體流程如下：

• 初始化一個棧和一個用於拼接當前字符串的變量。
• 遍歷字符串的每個字符：
• 遇到左括號“(”時，將當前字符串壓入棧中，並清空當前字符串以開始處理括號內內容。
• 遇到右括號“)”時，將當前字符串反轉後與棧頂字符串拼接，更新當前字符串。
• 其他字符則直接添加到當前字符串中。
• 遍歷結束後，當前字符串即為最終結果。

PHP代碼示例

function reverseParentheses($s) {
    $stack = [];
    $currentString = "";
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if ($char === '(') {
            array_push($stack, $currentString);
            $currentString = "";
        } elseif ($char === ')') {
            $currentString = strrev($currentString);
            if (!empty($stack)) {
                $currentString = array_pop($stack) . $currentString;
            }
        } else {
            $currentString .= $char;
        }
    }
    return $currentString;
}

// 示例調用
echo reverseParentheses("(abc)de(fgh)"); // 輸出 cbadehgf

性能分析

該方法的時間複雜度為O(n)，n 為輸入字符串長度，因為每個字符被訪問一次。空間複雜度也為O(n)，用於存儲棧和當前字符串。

總結

利用棧結構反轉括號內的子字符串是解決此類問題的高效方案。本文介紹的思路與代碼示例，適合在實際項目中遇到類似字符串處理需求時參考應用，幫助開發者提升編碼效率與問題解決能力。