[LeetCode] 2116. Check if a Parentheses String Can Be Valid
2022/7/2 6:20:07
本文主要是介绍[LeetCode] 2116. Check if a Parentheses String Can Be Valid,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A parentheses string is a non-empty string consisting only of '('
and ')'
. It is valid if any of the following conditions is true:
- It is
()
. - It can be written as
AB
(A
concatenated withB
), whereA
andB
are valid parentheses strings. - It can be written as
(A)
, whereA
is a valid parentheses string.
You are given a parentheses string s
and a string locked
, both of length n
. locked
is a binary string consisting only of '0'
s and '1'
s. For each index i
of locked
,
- If
locked[i]
is'1'
, you cannot changes[i]
. - But if
locked[i]
is'0'
, you can changes[i]
to either'('
or')'
.
Return true
if you can make s
a valid parentheses string. Otherwise, return false
.
Example 1:
Input: s = "))()))", locked = "010100" Output: true Explanation: locked[1] == '1' and locked[3] == '1', so we cannot change s[1] or s[3]. We change s[0] and s[4] to '(' while leaving s[2] and s[5] unchanged to make s valid.
Example 2:
Input: s = "()()", locked = "0000" Output: true Explanation: We do not need to make any changes because s is already valid.
Example 3:
Input: s = ")", locked = "0" Output: false Explanation: locked permits us to change s[0]. Changing s[0] to either '(' or ')' will not make s valid.
Constraints:
n == s.length == locked.length
1 <= n <= 105
s[i]
is either'('
or')'
.locked[i]
is either'0'
or'1'
.
判断一个括号字符串是否有效。
一个括号字符串是只由 '(' 和 ')' 组成的 非空 字符串。如果一个字符串满足下面 任意 一个条件,那么它就是有效的:
字符串为 ().
它可以表示为 AB(A 与 B 连接),其中A 和 B 都是有效括号字符串。
它可以表示为 (A) ,其中 A 是一个有效括号字符串。
给你一个括号字符串 s 和一个字符串 locked ,两者长度都为 n 。locked 是一个二进制字符串,只包含 '0' 和 '1' 。对于 locked 中 每一个 下标 i :如果 locked[i] 是 '1' ,你 不能 改变 s[i] 。
如果 locked[i] 是 '0' ,你 可以 将 s[i] 变为 '(' 或者 ')' 。
如果你可以将 s 变为有效括号字符串,请你返回 true ,否则返回 false 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/check-if-a-parentheses-string-can-be-valid
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
遇到括号配对的题,大概率会涉及到stack,以及需要从左往右 + 从右往左扫两遍。这么做的目的是抓到多余的左括号和多余的右括号。这道题的思路也很接近,不过这道题多给了一个数组 locked,表示可以改动的括号的方向。我们的做法依然还是扫两遍,第一遍我们从左往右扫描,扫描的时候我们用一个变量 count 统计左括号和可以改动的括号(locked.charAt(i) == 0)的数量,这样当我们遇到右括号的时候,我们可以把左括号抵消。当左括号被抵消完毕之后,我们可以再用那些可以改动的括号来抵消更多的右括号,直到那些可以改动的括号被用完为止。
第二遍从右往左扫描的时候,我们用变量 count 统计右括号和可以改动的括号(locked.charAt(i) == 0)的数量,这样当我们遇到左括号的时候,我们可以把右括号抵消。思路跟第一遍一样只是括号方向相反。
最后还有一个例外情况是如果统计到的半括号 + 可以改动的半括号的数量是奇数,就说明括号是无法成对的,就返回 false。
时间O(n)
空间O(n)
Java实现
1 class Solution { 2 public boolean canBeValid(String s, String locked) { 3 char[] words = s.toCharArray(); 4 char[] lock = locked.toCharArray(); 5 int len = s.length(); 6 // 记录左括号 + 可以改变的括号数量 7 int count = 0; 8 for (int i = 0; i < len; i++) { 9 if (lock[i] == '0') { 10 count++; 11 } else { 12 if (words[i] =='(') { 13 count++; 14 } else { 15 count--; 16 } 17 // 如果右括号多到左括号 + 可以改的括号都cover不住了就return false 18 if (count < 0) { 19 return false; 20 } 21 } 22 } 23 24 // corner case 25 if (count % 2 == 1) { 26 return false; 27 } 28 29 // 记录右括号 + 可以改变的括号数量 30 count = 0; 31 for (int i = len - 1; i >= 0; i--) { 32 if (lock[i] == '0') { 33 count++; 34 } else { 35 if (words[i] == '(') { 36 count--; 37 } else { 38 count++; 39 } 40 // 如果左括号多到右括号 + 可以改的括号都cover不住了就return false 41 if (count < 0) { 42 return false; 43 } 44 } 45 } 46 if (count % 2 == 1) { 47 return false; 48 } 49 return true; 50 } 51 }
LeetCode 题目总结
这篇关于[LeetCode] 2116. Check if a Parentheses String Can Be Valid的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升