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)。