20. Valid Parentheses
Easy
Topics
Companies
Hint
Given a string s 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.
Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.
Code
package main
import "fmt"
func main() {
fmt.Println( isValid("[([])]") )
}
type Stack struct {
data []string
}
func (s *Stack) push(v string) {
s.data = append(s.data, v)
}
func (s *Stack) pop() string {
if len(s.data) == 0 {
return ""
}
v := s.data[len(s.data)-1]
s.data = s.data[:len(s.data)-1]
return v
}
func isValid(s string) bool {
if s == "" {
return true
}
stack := Stack{}
for _, v := range s {
if v == '(' || v == '[' || v == '{' {
stack.push(string(v))
} else {
if len(stack.data) == 0 {
return false
}
top := stack.pop()
if (v == ')' && top != "(") || (v == ']' && top != "[") || (v == '}' && top != "{") {
return false
}
}
}
return true
}
