0020. Valid Parentheses

題目

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 '()[]{}'.

題目大意

解題思路

Big O

時間複雜 : 空間複雜 :

來源

• https://leetcode.com/problems/valid-parentheses/
• https://leetcode.cn/problems/valid-parentheses/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0020.Valid-Parentheses/main.go

package validparentheses

type Stack struct {
    runes []rune
}

func NewStack() *Stack {
    return &Stack{runes: []rune{}}
}

func (s *Stack) Push(str rune) {
    s.runes = append(s.runes, str)
}

func (s *Stack) Pop() rune {
    str := s.runes[len(s.runes)-1]
    s.runes = s.runes[:len(s.runes)-1]
    return str
}

// 時間複雜 O(n), 空間複雜 O(n)
func IsValid(s string) bool {
    runeStack := NewStack()
    for _, v := range s {
        // fmt.Println(string(v))
        if v == '(' || v == '[' || v == '{' {
            runeStack.Push(v)
        } else if (v == ')' && len(runeStack.runes) > 0 && runeStack.runes[len(runeStack.runes)-1] == '(') || (v == ']' && len(runeStack.runes) > 0 && runeStack.runes[len(runeStack.runes)-1] == '[') || (v == '}' && len(runeStack.runes) > 0 && runeStack.runes[len(runeStack.runes)-1] == '{') {
            runeStack.Pop()
        } else {
            return false
        }
    }
    return len(runeStack.runes) == 0
}

Benchmark