CODEWITHSUNDEEP
algorithm
Subodh Gupta
Subodh Gupta

Reputation: 193

given string of braces both open and closed tell if it's a valid string

This is the very simple in O(n) but I was asked to do it in less than O(n) time complexity.

e.g. 

{({})} 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

Upvotes: 2

Views: 548

Answers (2)

akalenuk
akalenuk

Reputation: 3845

You could of precalculate all the good strings for some reasonable length, put them in a huge hash table (not that huge actually, for instance all the good combinations for up to 12-character string would take only 10066 cells) and then do every check simply by looking into that table.

This could work for small strings and would of been very effective in general case, but... in the worse case it is still O(n).

Upvotes: 0

nicky_zs
nicky_zs

Reputation: 3773

If n is the length of the string, the algorithm complexity can't be less than O(n), because if there is any character the algorithm didn't check, it can't be sure of whether the character is a brace or not. So, it can't be less than O(n).

Upvotes: 2

Related Questions