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

難度：中

主題：字串、堆疊、貪婪

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

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

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

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

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

範(fàn)例1：

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

範(fàn)例2：

• 輸入： s = "()()"，鎖定 = "0000"
• 輸出： true
• 說明：我們不需要進(jìn)行任何更改，因?yàn)?s 已經(jīng)有效。

範(fàn)例 3：

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

約束：

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

提示：

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

解：

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

要點(diǎn)：

1. 如果字串的長度是奇數(shù)，我們可以立即傳回 false，因?yàn)橛行У睦ㄌ栕执仨毦哂信紨?shù)長度（每個(gè)開頭（需要一個(gè)結(jié)尾））。
2. 當(dāng)我們迭代字串時(shí)，我們需要追蹤左括號 (() 和右括號 ()) 的數(shù)量。如果在任何時(shí)候右括號的數(shù)量超過了左括號的數(shù)量，就不可能平衡字串，我們回傳 false。
3. 我們必須小心處理鎖定（locked[i] == '1'）和解鎖（locked[i] == '0'）的部位。解鎖的位置允許我們改變角色，但鎖定的位置則不能。

演算法:

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

讓我們用 PHP 實(shí)作這個(gè)解：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. 第一遍（由左至右）：

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

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

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

3. 邊緣情況：如果字串長度為奇數(shù)，我們立即傳回 false，因?yàn)樗鼰o法形成有效的括號字串。

時(shí)間複雜度：

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

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

聯(lián)絡(luò)連結(jié)

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個(gè)星號或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是檢查括號字串是否有效的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！