Skip to content

20-valid-parentheses.md

Latest commit

聽

History

History
135 lines (106 loc) 路 3.49 KB

20-valid-parentheses.md

File metadata and controls

135 lines (106 loc) 路 3.49 KB
Raw

20. Valid Parentheses - Best Practices of LeetCode Solutions

LeetCode link: 20. Valid Parentheses, difficulty: Easy

LeetCode description of "20. Valid Parentheses"

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

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. 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

[Example 4]

Input: s = "([])"

Output: true

[Constraints]

  • 1 <= s.length <= 10000
  • s consists of parentheses only ()[]{}.

Hints

Hint 1 Use a stack of characters.
Hint 2 When you encounter an opening bracket, push it to the top of the stack.
Hint 3 When you encounter a closing bracket, check if the top of the stack was the opening for it. If yes, pop it from the stack. Otherwise, return false.

Intuition

  1. Bracket matching focuses on the previous character and the current character. There are two situations to consider:
    1. If the current character is a left bracket, there is no need to match it and it can be saved directly.
    2. If the current character is a right bracket, and the previous character and the current character are paired, both characters can disappear; otherwise, if the pairing fails, false is returned directly.
  2. This scenario that focuses on the previous character and the current character is suitable for implementation with a stack.
  3. The mapping relationship between left and right brackets can be saved in a Map.
  4. Finally, if the stack is empty, it means that all pairings are successful and true is returned; otherwise, false is returned.

Complexity

  • Time: O(N).
  • Space: O(N).

JavaScript

var isValid = function (s) {
  const rightToLeft = new Map([
    [')', '('],
    ['}', '{'],
    [']', '['],
  ])
  const stack = []

  for (const char of s) {
    if (!rightToLeft.has(char)) {
      stack.push(char)
    } else if (stack.length === 0 || stack.pop() != rightToLeft.get(char)) {
      return false
    }
  }

  return stack.length === 0
};

Python

class Solution:
    def isValid(self, s: str) -> bool:
        right_to_left = {
            ')': '(',
            '}': '{',
            ']': '[',
        }
        stack = []

        for char in s:
            if char not in right_to_left:
                stack.append(char)
            elif not stack or stack.pop() != right_to_left[char]:
                return False

        return not stack

Java

// Welcome to create a PR to complete the code of this language, thanks!

C++

// Welcome to create a PR to complete the code of this language, thanks!

C#

// Welcome to create a PR to complete the code of this language, thanks!

Go

// Welcome to create a PR to complete the code of this language, thanks!

Ruby

# Welcome to create a PR to complete the code of this language, thanks!

C, Kotlin, Swift, Rust or other languages

// Welcome to create a PR to complete the code of this language, thanks!