As the title suggests, here is my solution for A Programming Job Interview Challenge #13 – Brackets
Your input is a string which is composed from bracket characters. The allowed characters are:’(‘, ‘)’, ‘[‘. ‘]‘, ‘{’, ‘}’, ‘< ’ and ‘>’. Your mission is to determine whether the brackets structure is legal or not.
Example of a legal expression: “([](< {}>))â€.
Example of an illegal expression: “({< )>}â€.
Provide the most efficient, elegant and simple solution for that problem.I think that this is a well known problem but I am not sure, so excuse me if this week’s question is screwed.
I think this one is rather easy….unless i missed something…..
So to start with, you have a dictionary/hashtable and a stack. The dictionary keys consist of all opening bracket characters (ie: “(, [, <, {” ), and the corresponding values for each key are the closing bracket characters (ie: “), ], >, }”).
Now the process itself is to iterate over the string from left to right, and look up the current character in the dictionary.
- If the current character is an opening bracket, get the corresponding close bracket, push it on the stack and move on.
- If it is not an opening bracket, then pop the current closing bracket off the stack.
- If the popped character is the same as the current character, then move on (ie: valid closing bracket match).
- If the popped character is NOT the same as the current character, then we’ve hit a broken sequence and error out here.
There is some fine-tuning that would need to be done in the case where the input sequence commenced with a closing bracket and there is nothing in the stack, but what you see is basically it. 🙂 Simple and elegant IMO.
Thank God i don’t need to explain the mathematical complexity of this one…I really wouldn’t know where to start.
Don’t know the complexity?
You perform a fixed number of steps on each character, so we start with O(n * X).
So, now we only have to determine X. For each character, we:
– lookup a character in a dictionary/hashtable, we we determined in a previous Dev102 challenge is either O(1) or O(ln N) depending on the algorithm used.
– push or pop a value from a stack: O(1).
Put them all together, we have N * 1 * 1 or N * ln N * 1. O(N) or prehaps O(N ln N).
Of course, being O(N) isn’t the final word on efficiency. It merely means that the time it taken in given by the function:
T = C*N + K, and your C value (X in the above analysis) is rather high. (O(1) merely means that value is fixed, not that it is low).
I gave the full code on mine at http://www.honestillusion.com
(EDIT: fixed URL link a the bottom)