檢查括號字串是否有效

2116。檢查括號字串是否有效

難度：中

主題：字串、堆疊、貪婪

括號字串是僅由「(」和「)」組成的非空字串。滿足以下任一條件即有效：

• 是()。
• 可以寫為AB（A與B連接），其中A和B是有效的括號字串。
• 可以寫成 (A)，其中 A 是有效的括號字串。

給你一個括號字串 s 和一個鎖定字串，長度都是 n。 lock 是一個僅由「0」和「1」組成的二進位字串。對於每個鎖定的索引i，

• 如果locked[i]為“1”，您不能更改s[i]。
• 但是如果locked[i]是'0'，你可以將s[i]改為'('或')'。

如果可以使 s 成為有效的括號字串，則傳回 true。否則，返回 false。

範例1：

• 輸入： s = "))()))"，鎖定 = "010100"
• 輸出： true
• 解釋：locked[1] == '1' 且locked[3] == '1'，因此我們無法更改s[1] 或s[3]。
  • 我們將 s[0] 和 s[4] 改為 '('，同時保持 s[2] 和 s[5] 不變以使 s 有效。

範例2：

• 輸入： s = "()()"，鎖定 = "0000"
• 輸出： true
• 說明：我們不需要進行任何更改，因為 s 已經有效。

範例 3：

• 輸入： s = ")"，鎖定 = "0"
• 輸出： false
• 解釋： 鎖定允許我們更改 s[0]。
  • 將 s[0] 改為「(」或「)」不會使 s 有效。

約束：

• n == s.length == 鎖定.length
• 1 5
• s[i] 是 '(' 或 ')'。
• Locked[i] 為「0」或「1」。

提示：

1. 奇數長度的字串是否有效？
2. 從左到右，如果遇到鎖定的')'，則必須與其左側鎖定的'('或未鎖定的索引平衡。如果都不存在，可以得出什麼結論？如果都存在，哪個更適合使用？
完成上述操作後，我們可能已經鎖定了「(」的索引以及其他未鎖定的索引。現在如何平衡鎖定的「(」？如果無法平衡任何鎖定的「(」怎麼辦？

解：

我們可以一步步接近它，同時牢記鎖定部位的限制和行為。

要點：

1. 如果字串的長度是奇數，我們可以立即傳回 false，因為有效的括號字串必須具有偶數長度（每個開頭（需要一個結尾））。
2. 當我們迭代字串時，我們需要追蹤左括號 (() 和右括號 ()) 的數量。如果在任何時候右括號的數量超過了左括號的數量，就不可能平衡字串，我們回傳 false。
3. 我們必須小心處理鎖定（locked[i] == '1'）和解鎖（locked[i] == '0'）的部位。解鎖的位置允許我們改變角色，但鎖定的位置則不能。

演算法:

• 第1步：檢查字串s的長度是否為奇數。如果是，立即回傳 false。
• 第 2 步： 從左到右循環字串以追蹤括號的平衡情況。
  • 使用計數器來追蹤左（和右）括號之間的平衡。
  • 如果在任何時候，右括號的數量超過左括號的數量，請檢查鎖定位置是否有足夠的靈活性來平衡它。
  • 處理完整個字串後，檢查括號是否平衡，即是否沒有剩餘不符的左括號。

讓我們用 PHP 實作這個解：2116。檢查括號字串是否有效

<?php /**
 * @param String $s
 * @param String $locked
 * @return Boolean
 */
function canBeValid($s, $locked) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$s = "))()))";
$locked = "010100";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = "()()";
$locked = "0000";
var_dump(canBeValid($s, $locked));  // Output: bool(true)

$s = ")";
$locked = "0";
var_dump(canBeValid($s, $locked));  // Output: bool(false)
?>

解釋：

1. 第一遍（由左至右）：

   • 我們迭代字串並追蹤左括號的餘額。每次遇到左括號（，我們都會增加開計數器。對於閉括號），我們會減少開計數器。
   • 如果當前字元被解鎖（locked[i] == '0'），我們可以假設它是 ( 如果需要平衡括號。
   • 如果在任何時候開放計數器變為負數，則表示我們的右括號多於左括號，並且我們返回 false。

2. 第二遍（由右至左）：

   • 我們反向執行類似的操作來處理可能位於字串末尾的不匹配左括號的情況。
   • 這裡我們用閉計數器追蹤右括號 ()) 並確保不存在不平衡的括號。

3. 邊緣情況：如果字串長度為奇數，我們立即傳回 false，因為它無法形成有效的括號字串。

時間複雜度：

• 兩次傳遞（從左到右和從右到左）都需要線性時間 O(n)，其中 n 是字串的長度。因此，總體時間複雜度為 O(n)，這對於輸入大小限制是有效的。

這個解在給定的限制下正確處理了問題。

聯絡連結

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

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

• 領英
• GitHub

以上是檢查括號字串是否有效的詳細內容。更多資訊請關注PHP中文網其他相關文章！