algorithm - 常数空间和线性时间平衡括号算法是否存在？

Question

我知道我们可以通过在线性时间内使用堆栈来检查括号是否在字符串中平衡。但我在一次采访中被问到，我必须使用恒定空间在线性或更短的时间内完成这项工作。我想不出办法来做到这一点。有人有想法么？

标签： algorithm

Answer 1

跟踪到目前为止已经看到多少个左括号减去多少个右括号。如果它低于零，则您的右括号与之前的左括号不匹配。如果最后不为零，则您有一个不匹配的左括号。