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