[Go] LeetCode 20. Valid Parentheses
1 min readJan 21, 2020
Description
Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
Solution
/* Approach 1: Stacks */
func makeParMap() map[string]string{
parMap := make(map[string]string)
parMap["}"] = "{"
parMap["]"] = "["
parMap[")"] = "("
return parMap
}func isValid(s string) bool {
var stack []string
for i := 0; i < len(s); i++{
char := string(s[i])
parMap := makeParMap()
if _,ok := parMap[char]; ok{
if len(stack) == 0 {
return false
}n := len(stack)-1
pop := stack[n]
if parMap[char] != pop{
return false
}//pop
stack = stack[:n]
continue
}
//push
stack = append(stack,char)
}
return len(stack) == 0
}