LeetCode-20. Valid Parentheses | 有效的括号

题目

LeetCode
LeetCode-cn

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.

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
Example 4:

Input: s = "([)]"
Output: false
Example 5:

Input: s = "{[]}"
Output: true
 

Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

题解

这道题是经典的考察栈的题目。

解法一：使用strings.Replace替换为空

直接用strings.Replace方法，将()、[]、{}这样的字符串替换为空，如果最后全都可以替换掉，说明是有效字符串，返回true，否则返回false。

//Go
func isValid(s string) bool {
    if len(s)%2 == 1 {
		return false
	}
	for len(s) != 0 {
		temp := s
		s = strings.Replace(s, "()", "", -1)
		s = strings.Replace(s, "[]", "", -1)
		s = strings.Replace(s, "{}", "", -1)

		if s == temp {
			return false
		}
	}

	return true
}

执行结果：

leetcode-cn执行：
执行用时：4 ms, 在所有 Go 提交中击败了6.50%的用户
内存消耗：7.1 MB, 在所有 Go 提交中击败了5.26%的用户

leetcode执行：
Runtime: 4 ms, faster than 5.19% of Go online submissions for Valid Parentheses.
Memory Usage: 7 MB, less than 7.32% of Go online submissions for Valid Parentheses.

解法二：栈

//Go
func isValid(s string) bool {
    //考虑空字符串的特殊情况
    if s == "" {
		return true
	}
    //定义一个栈
	stack := make([]int32, len(s))
    length := 0
    //判断括号是否匹配
    for _,v := range s {
        if v == '(' || v == '[' || v == '{' {
            //左括号，入栈
            stack[length] = v
            length++
        } else {
            //右括号，比较栈顶，匹配则移除，不匹配就返回false
            if length == 0 {
                return false
            }
            if (v == ')' && stack[length-1] == '(') || (v == ']' && stack[length-1] == '[') || (v == '}' && stack[length-1] == '{') {
                length--
            } else {
                return false
            }
        }
    }

    return length == 0
}

执行结果：

leetcode-cn执行：
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了72.86%的用户

leetcode执行：
Runtime: 0 ms, faster than 100.00% of Go online submissions for Valid Parentheses.
Memory Usage: 2 MB, less than 98.88% of Go online submissions for Valid Parentheses.