Problem overview
The function isValid receives a string made only of the characters (, ), {, }, [ and ]. It returns true when the string is valid and false otherwise. A string is valid when every opening bracket is closed by a bracket of the same type, and the brackets are closed in the right order: the most recently opened one must be closed first.
Take the examples. "()[]{}" is valid: each bracket is closed right after it opens. "{[]}" is valid because the inner pair closes before the outer one. "(]" is invalid because the types differ, and "([)]" is invalid because the ) arrives while the [ opened later is still open. The input has between 1 and 10,000 characters, and the lesson asks for O(n) time and O(n) extra space.
Approach: a stack of open brackets
The rule "the last opened bracket must close first" is exactly how a stack behaves: last in, first out. Walk through the string from left to right:
- An opening bracket is pushed onto the stack. It waits for its partner.
- A closing bracket must match the bracket on top of the stack. Pop the top and compare. If the stack is empty, or the types differ, the string is invalid.
- When the walk ends, the stack must be empty. Anything left was opened and never closed.
A simpler idea, counting the opening and closing brackets of each type, accepts "([)]", because the counts balance even though the order is wrong. The stack keeps the order, which is why it is needed.
Each character is pushed at most once and popped at most once, so the work is linear.
Step by step
- Build a lookup table named
closingBrackets, amap[byte]bytefrom each opening bracket to the closing bracket that matches it. It does two jobs: its keys tell opening brackets from closing ones, and its values say what must close each opener. - Create the stack as an empty slice of bytes. The end of the slice is the top.
- Loop over the indices of
inputwith a classicforloop and take the current character asbracket := input[i]. - Check whether it is an opener with the two-value map lookup. Only the
okflag matters, so the value is ignored with_. - Push openers with
append, assigning the result back tostack. - Handle closers in the
elsebranch. First, if the stack is empty there is nothing to match, so returnfalse. - Read the top at index
len(stack)-1and pop it by reslicing tostack[:len(stack)-1]. - Compare. The only valid closer for that opener is
closingBrackets[openBracket]. Ifbracketis anything else, returnfalse. - After the loop, return whether the stack is empty. Leftover openers make the string invalid.
The solution in Go
func isValid(input string) bool {
closingBrackets := map[byte]byte{
'(': ')',
'{': '}',
'[': ']',
}
stack := []byte{}
for i := 0; i < len(input); i++ {
bracket := input[i]
if _, ok := closingBrackets[bracket]; ok {
stack = append(stack, bracket)
} else {
if len(stack) == 0 {
return false
}
openBracket := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if bracket != closingBrackets[openBracket] {
return false
}
}
}
return len(stack) == 0
}
The Go details worth a closer look:
- Indexing a string gives a byte.
input[i]has typebyte(an alias ofuint8), not a character. Printing it shows a number:"("[0]prints as 40. That is why the map ismap[byte]byte, and why the literal keys such as'('work: an untyped rune constant that fits in a byte converts tobyteautomatically. Bytes are enough here because every bracket is a single byte. - The comma-ok lookup. Reading a missing key from a map does not fail; it returns the zero value, here 0.
_, ok := closingBrackets[bracket]asks the question directly, andokisfalsefor a key that is absent. Declaringokin theifheader limits it to that statement. - The slice as a stack.
appendmay allocate a bigger backing array, so its result always goes back intostack. The pop,stack[:len(stack)-1], copies nothing: it shortens the length and leaves the old element behind in the array, which is harmless here. elseplacement. Go requireselseon the same line as the closing brace of theif.- Returning a comparison.
len(stack) == 0is already abool, so noifis needed.
Complexity
Time: O(n). The loop visits each character once, and a map lookup, a push and a pop each take constant time on average.
Space: O(n). In the worst case, such as "((((((", every character is an opener and the stack grows to n elements. The map holds three fixed entries.
Edge cases and common mistakes
- A closer with an empty stack. For
")"or"())"the stack is empty when the closer arrives. Readingstack[len(stack)-1]would then index position -1 and panic, so the emptiness check must come first. - Leftover openers.
"("and"(()"pass every comparison in the loop. Only the finallen(stack) == 0rejects them. - Odd length. A valid string always has an even length, since brackets come in pairs. The stack logic already handles this, but it explains why
"((("can never be valid. - Counting instead of stacking. Checking only that each type appears equally often wrongly accepts
"([)]". - Comparing the wrong pair. The popped opener is the key in the map, so the comparison is
bracket != closingBrackets[openBracket]. ComparingbracketwithopenBracketitself would fail every valid string. - Using a
stringfor the map. Withinput[i]as the lookup key, amap[string]stringdoes not compile, because a byte is not a string.
Testing
"()"givestrue."()[]{}"givestrue."{[]}"givestrue."(]"givesfalse."([)]"givesfalse."(("givesfalse.")"givesfalse.