。使括號有效的最小添加量

921。使括號有效的最少添加

難度：中

主題：字串、堆疊、貪婪

括號字串有效當且僅當：

• 它是空字串，
• 可以寫為AB（A與B連接），其中A和B是有效字串，或
• 可以寫成(A)，其中A是一個有效的字串。

給你一個括號字串 s。一步操作即可在字串的任意位置插入括號。

• 例如，如果 s = "()))"，則可以插入左括號「(()))」或右括號「())))」。

返回使 s 有效所需的最小移動次數.

範例1：

• 輸入： s = "())"
• 輸出： 1

範例2：

• 輸入： s = "(("
• 輸出： 3

約束：

• 1
• s[i] 是 '(' 或 ')'。

解：

我們需要確定需要增加多少個左括號或右括號才能讓輸入字串有效。有效的字串意味著每個左括號 '(' 都有對應的右括號 ')'。

我們可以用簡單的計數器方法來解決這個問題：

• 我們使用變數balance來追蹤左括號和右括號之間的當前平衡。
• 我們使用另一個變數加法來計算所需的最小括號數。

方法：

1. 循環遍歷字串 s 的每個字元。
2. 如果字元是“(”，則餘額加 1。
3. 如果字元是')'，則餘額減1：
   • 如果餘額變成負數，則表示右括號比左括號多。我們需要添加一個左括號來平衡它，因此將加法加 1 並將餘額重設為 0。
4. 循環結束時，如果balance大於0，表示有不匹配的左括號，所以加上balance。

讓我們用 PHP 實作這個解：921。使括號有效的最少添加

<?php
/**
 * @param String $s
 * @return Integer
 */
function minAddToMakeValid($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s1 = "())";
echo minAddToMakeValid($s1);  // Output: 1

$s2 = "(((";
echo minAddToMakeValid($s2);  // Output: 3
?>

解釋：

• 對於字串 s = "())"：
  • 當遇到第二個 ')' 時，餘額變成負數，因此添加量會增加。
  • 最後餘額為0，加法為1，所以我們需要加1才能讓字串有效。
• 對於字串 s = "(((":
  • 餘額變成 3，因為末尾有 3 個不匹配的「(」。
  • 結果是加法餘額，即 0 3 = 3。

此解的時間複雜度為O(n)，其中n 是字串的長度，還有一個空格O(1) 的複雜度，因為我們只用了幾個變數。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。使括號有效的最小添加量的詳細內容。更多資訊請關注PHP中文網其他相關文章！