首页 > 代码库 > 【算法】 小知识
【算法】 小知识
记录一些在我看来有意思的小算法知识
■ 识别有效的括号字符串
以小括号为例,在带括号的字符串中,如果只提取出括号作为特征,"()",""(空串),"(()(()(())))"这些是有效的括号字符串,虽然有嵌套但是没有乱套,每个左括号都可以找到正确的右括号配对
而")(())","(((","("等这些字符串就是非法的
有效的括号字符串的要求应该有1.左括号和右括号数量应该相等 2. 不能有多余的右括号出现在左括号的左边。
在网上看到一个很聪明的方法就是:
从头开始扫描字符串,设置count=0,每扫描一个字符,如果是左括号就count+=1,如果是右括号count-=1,只要保证扫描过程中count始终不为负且count最终==0就表明字符串合法
另外一种方法,适用不仅仅是小括号,中、大括号也存在时的情况:
while True:不断去掉字符串中相邻的括号对,也就是说replace("()",""),replace("[]",""),replace("{}",""),一直到没有任何相邻括号对存在为止。此时如果字符串已经成为空串那么表明其是有效括号字符串,否则为无效。
【算法】 小知识
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。