→ Rushia: 你板剩我剩我花式吃WA了 01/12 16:54
→ sustainer123: 我前面卡超久 在想怎寫判斷條件 後面發現理解錯題意 01/12 16:55
→ Meaverzt: 看懂題目花超久：0 01/12 16:55
※ 引述《dont (dont)》之銘言：
: 2116. Check if a Parentheses String Can Be Valid
: ## 思路
: 記錄還沒配對的括號個數 open
: 把locked==0的也當作 `(`
: 如果遇到配對不了的括號 就回傳FALSE
: 兩個方向各掃一遍
: ## Code
: ```cpp
: class Solution {
: public:
: bool canBeValid(string s, string locked) {
: int n = s.size();
: if (n & 1) return false;
: int open = 0;
: for (int i=0; i<n; ++i) {
: if (locked[i] == '0' || s[i] == '(') {
: ++open;
: } else if (open == 0) {
: return false;
: } else {
: --open;
: }
: }
: open = 0;
: for (int i=n-1; i>=0; --i) {
: if (locked[i] == '0' || s[i] == ')') {
: ++open;
: } else if (open == 0) {
: return false;
: } else {
: --open;
: }
: }
: return true;
: }
: };
: ```
思路:
1.len(s) % 2 == 1一定不平衡
2.先前向遍歷，確認是否有足夠的(匹配)
3.最後反向遍歷，確認是否有足夠的)匹配(
Python Code:
class Solution:
def canBeValid(self, s: str, locked: str) -> bool:
left = 0
right = 0
n = len(s)
if n % 2 == 1:
return False
for i in range(n):
if s[i] == "(" or locked[i] == "0":
left += 1
else:
left -= 1
if left < 0:
return False
for i in range(n-1,-1,-1):
if s[i] == ")" or locked[i] == "0":
right += 1
else:
right -= 1
if right < 0:
return False
return True
AB卡我好久 看Constraints才發現問題 不難
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736671973.A.F69.html