如何找到圆括号，大括号和方括号的字符串的有效性？ [英] How to find validity of a string of parentheses, curly brackets and square brackets?
问题描述
最近，我在这个有趣的问题接触。您将获得只包含字符的字符串（，'）， {，'} ，[和 ]，例如[{（）}]，你需要编写一个函数，它会检查这样的输入的有效性字符串函数可能是这样的：
BOOL的isValid（字符* S）;
这些支架必须关闭以正确的顺序，例如（）和（）[] {}都是有效的，但（]，（[）]和 {{{{都没有！
I recently came in contact with this interesting problem. You are given a string containing just the characters '(', ')', '{', '}', '[' and ']', for example, "[{()}]", you need to write a function which will check validity of such an input string, function may be like this:
bool isValid(char* s);
these brackets have to close in the correct order, for example "()" and "()[]{}" are all valid but "(]", "([)]" and "{{{{" are not!
我想出了下面的O（n）时间及O（n）的空间复杂度的解决方案，它工作正常：
I came out with following O(n) time and O(n) space complexity solution, which works fine:
- 在维护一个堆栈的字符。
- 当你发现打开括号
（，'{'或[将其推入堆栈。 - 无论何时你发现右括号
'），'}或']，请检查堆栈的顶部对应左括号，如果是，则弹出栈，否则打破循环和返回false。 - 重复步骤2 - 3直到字符串结尾 。
- Maintain a stack of characters.
- Whenever you find opening braces
'(','{'OR'['push it on the stack. - Whenever you find closing braces
')','}'OR']', check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false. - Repeat steps 2 - 3 until end of the string.
这工作，但我们可以优化它的空间，可以是恒定的额外的空间，我明白，时间复杂度不能低于O（N），因为我们要看看每一个角色。
This works, but can we optimize it for space, may be constant extra space, I understand that time complexity cannot be less than O(n) as we have to look at every character.
我的问题是，我们才能解决O（1）空间这个问题呢？
So my question is can we solve this problem in O(1) space?
推荐答案
其实，有一个确定的日志空间算法由于Ritchie和Springsteel：<一href="http://dx.doi.org/10.1016/S0019-9958(72)90205-7">http://dx.doi.org/10.1016/S0019-9958(72)90205-7 （<打击> paywalled，遗憾不在线）。因为我们需要登录比特来索引串，这是空间最优
Actually, there's a deterministic log-space algorithm due to Ritchie and Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 (paywalled, sorry not online). Since we need log bits to index the string, this is space-optimal.
如果你愿意接受片面的错误，那么就认为用电量polylog（n）时间和polylog（n）的空间的算法：<一href="http://www.eccc.uni-trier.de/report/2009/119/">http://www.eccc.uni-trier.de/report/2009/119/
If you're willing to accept one-sided error, then there's an algorithm that uses n polylog(n) time and polylog(n) space: http://www.eccc.uni-trier.de/report/2009/119/
这篇关于如何找到圆括号，大括号和方括号的字符串的有效性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
