阅读 84

Google 面试题 | 有效括号字符串

专栏 | 九章算法

网址 | http://www.jiuzhang.com

image

题目描述

给定一个字符串,由( * )三个字符组成,判断是否满足要求左括号和有括号一一对应,
且对应的左括号必定在右括号前面。其中,*可以被当做一个单独的左括号,右括号或者可
以当做不存在
复制代码

样例

1. **Input**: "()"            **Output**: True

2. **Input**: "(*)"          **Output**: True      //*被当做空字符,不存在

3. **Input**: "(*))"         **Output**: True     //星号被当做左括号
复制代码

解题思路分析

首先进行最基础的考虑,(在不考虑星号的情况下)我们必定会选择位置最接近的左右括号配对,这样
避免了人为造成的右括号前面没有左括号匹配的惨剧。因此我们在写程序进行处理的时候,对于每个右
括号判断前面是否有1个左括号能被他拥有,如果左括号数量不足,这个字符串必定是false,或者当整
个串被匹配完之后发现有多余的左括号,这个字符串同样是false
复制代码
接下来考虑有星号的情况:")"必须由位置在它之前的"(""*"匹配,如果"("或者"*"数量不足导致的
false是无法避免的,而如果"("")"多,将"(""*"优先匹配可以减小false的可能性。举个例子如
样例3,从左往右遍历的时候,优先匹配"(""*",遇见第一个")",发现没有单独的"(",从"(*"的组
合中拆出一个"("与之匹配,而原先匹配中的*因为可以等同于不存在便不予理会,接着遇到第二个”)”,
拿走刚才剩余的"*"。综上我们可以观察到,"("容易受制于")"而将其与"*"匹配后就很灵活,不仅避免
了数量太多带来的麻烦,也能在和*匹配后再次提供自身给")"进行匹配。而如果这样匹配结束还有多余
的"("则必定false
复制代码
我们设l(left)为必须被右括号匹配的左括号数量,cp(couple)为前面左括号和星号数量。遍历字
符串,遇到左括号和星号的时候,cp++;遇到右括号的时候cp—;遇到星号,默认先于前面的左括号(l>0)
匹配,此时(l—),遇到右括号,默认先与前面必须与右括号匹配的左括号匹配,此时(l—;cp—;)或者在支
援兵中考虑(cp—) 注意cp是前方左右的左括号和星号数量,一旦cp<0即false.匹配完发现(l>0)即多出
了左括号,也为false。剩下的情况就是true复制代码

参考程序

http://www.jiuzhang.com/solution/valid-parenthesis-string/
复制代码

image

面试官角度分析

一道简单的思维题,考虑到星号在其中的用处就能解决
复制代码

lintcode相关问题

http://www.jiuzhang.com/solutions/valid-parentheses
复制代码

image
分割线

欢迎关注我的微信公众号:九章算法(ninechapter)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等

评论