[LeetCode] 20. Valid Parentheses 合法括号

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 20. Valid Parentheses 合法括号,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid.html

An input string is valid if:java

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.python

Example 1:app

Input: "()"
Output: true

Example 2:ide

Input: "()[]{}"
Output: true

Example 3:post

Input: "(]"
Output: false

Example 4:url

Input: "([)]"
Output: false

Example 5:code

Input: "{[]}"
Output: true

输入的字符串只含有'('')''{''}''[' , ']',验证字符串是否配对合理。htm

解法:栈Stack,经典的使用栈的题目。遍历字符串,若是为左括号,将其压入栈中,若是遇到为右括号,若此时栈为空,则直接返回false,如不为空,则取出栈顶元素,若为对应的左括号,是合法的继续循环,不然返回false。blog

Java: Time: O(n), Space: O(n)

public static boolean isValid(String s) {
	HashMap<Character, Character> map = new HashMap<Character, Character>();
	map.put('(', ')');
	map.put('[', ']');
	map.put('{', '}');
	Stack<Character> stack = new Stack<Character>();
 
	for (int i = 0; i < s.length(); i++) {
		char curr = s.charAt(i); 
		if (map.keySet().contains(curr)) {
			stack.push(curr);
		} else if (map.values().contains(curr)) {
			if (!stack.empty() && map.get(stack.peek()) == curr) {
				stack.pop();
			} else {
				return false;
			}
		}
	} 
	return stack.empty();
}

Java:

public boolean isValid(String s) {
	Stack<Character> stack = new Stack<Character>();
	for (char c : s.toCharArray()) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.isEmpty() || stack.pop() != c)
			return false;
	}
	return stack.isEmpty();
}  

Python:

class Solution:
    # @return a boolean
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []  

Python: Time: O(n), Space: O(n)

class Solution:
    def isValid(self, s):
        stack, lookup = [], {"(": ")", "{": "}", "[": "]"}
        for parenthese in s:
            if parenthese in lookup:  # Cannot use if lookup[parenthese]: KeyError
                stack.append(parenthese)
            elif len(stack) == 0 or lookup[stack.pop()] != parenthese: # Cannot use not stack
                return False
        return len(stack) == 0

Python: wo

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        m = {'(': ')', '[': ']', '{': '}'}
        n = [')', ']', '}']
        for i in s:
            if i in m:
                stack.append(i)
            elif i in n and stack:
                if m[stack.pop()] != i:
                    return False
            else:
                return False
        return len(stack) == 0

C++:

class Solution {
public:
    bool isValid(string s) {
        stack<char> parentheses;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]);
            else {
                if (parentheses.empty()) return false;
                if (s[i] == ')' && parentheses.top() != '(') return false;
                if (s[i] == ']' && parentheses.top() != '[') return false;
                if (s[i] == '}' && parentheses.top() != '{') return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
}; 

  

相似题目:

[LeetCode] 22. Generate Parentheses

[LeetCode] 32. Longest Valid Parentheses

[LeetCode] 241. Different Ways to Add Parentheses

[LeetCode] 301. Remove Invalid Parentheses

 

All LeetCode Questions List 题目汇总