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