algorithm - 给定的大括号字符串打开和关闭告诉它是否是一个有效的字符串

Question

这在 O(n) 中非常简单，但我被要求在小于 O(n) 的时间复杂度内完成。

例如

{({})} is a valid string because each type of opening brace has a matching closing brace. 
while for {{{{)))} this is not as braces doesn't match  

Answer 1

如果 n 是字符串的长度，算法复杂度不能小于 O(n)，因为如果有任何字符算法没有检查，它不能确定该字符是大括号还是不是。因此，它不能小于 O(n)。

Answer 2

您可以预先计算出合理长度的所有好的字符串，将它们放入一个巨大的哈希表中（实际上并没有那么大，例如，最多 12 个字符的字符串的所有好的组合只需要 10066 个单元格），然后进行每次检查只需查看该表。

这可能适用于小字符串，并且在一般情况下会非常有效，但是......在更坏的情况下它仍然是 O(n)。