檢查括號字串是否有效-php教程-PHP中文網

檢查括號字串是否有效

DDD

發布： 2025-01-12 22:04:47

原創

517 人瀏覽過

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」。

提示：

奇數長度的字串是否有效？
從左到右，如果遇到鎖定的')'，則必須與其左側鎖定的'('或未鎖定的索引平衡。如果都不存在，可以得出什麼結論？如果都存在，哪個更適合使用？

解：

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

要點：

如果字串的長度是奇數，我們可以立即傳回 false，因為有效的括號字串必須具有偶數長度（每個開頭（需要一個結尾））。
當我們迭代字串時，我們需要追蹤左括號 (() 和右括號 ()) 的數量。如果在任何時候右括號的數量超過了左括號的數量，就不可能平衡字串，我們回傳 false。
我們必須小心處理鎖定（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)
?>

登入後複製

解釋：

第一遍（由左至右）：
- 我們迭代字串並追蹤左括號的餘額。每次遇到左括號（，我們都會增加開計數器。對於閉括號），我們會減少開計數器。
- 如果當前字元被解鎖（locked[i] == '0'），我們可以假設它是 ( 如果需要平衡括號。
- 如果在任何時候開放計數器變為負數，則表示我們的右括號多於左括號，並且我們返回 false。
第二遍（由右至左）：
- 我們反向執行類似的操作來處理可能位於字串末尾的不匹配左括號的情況。
- 這裡我們用閉計數器追蹤右括號 ()) 並確保不存在不平衡的括號。
邊緣情況：如果字串長度為奇數，我們立即傳回 false，因為它無法形成有效的括號字串。