README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0020. Valid Parentheses	https://leetcode.com/problems/valid-parentheses/	2023-01-22 21:20:00 +0800	2023-01-22 21:20:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0020.Valid-Parentheses			LeetCode Go Easy Valid Parentheses	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

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