leetcode
January 7, 2024

Viiisit [LeetCode] - 20. Valid Parentheses

#php#javascript#ruby

keep learning, keep coding!

Problem - 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.

翻譯蒟蒻

每個開放的括號，必須有一個相應的關閉括號，並且必須按照正確的順序配對。

定義一個 map 作為對照。
每當遇到左括號，就將其推入 stack 堆疊；每當遇到右括號，就從 stack 堆疊中彈出一個元素，並檢查彈出的元素是否與當前的右括號匹配。如果在任何時候都不匹配，則返回 false。如果遍歷完所有後 stack 堆疊為空，則返回 true。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var isValid = function(s) {
    let stack = []

    let map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }

    for (let i = 0; i < s.length; i++) {
        // 如果當前字符是左括號（在 map 中有對應的右括號）
        if (map[s[i]]) { 
            stack.push(s[i])
        } else {
            let pop = stack.pop()
            if (map[pop] !== s[i]) {
                return false
            }
        }
    }

    // 如果堆疊為空，表示所有的括號都已配對，返回 true。
    return stack.length === 0
};

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def is_valid(s)
  stack = []
  map = {
    '(' => ')',
    '[' => ']',
    '{' => '}'
  }
  s.each_char do |c|
    if map[c]
      stack << c
    else
      return false if map[stack.pop] != c
    end
  end
  stack.empty?
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isValid($s) {
  $stack = [];
  $map = [
    ')' => '(',
    ']' => '[',
    '}' => '{'
  ];
  for ($i = 0; $i < strlen($s); $i++) {
    if (in_array($s[$i], ['(', '[', '{'])) {
      array_push($stack, $s[$i]);
    } else {
      if (array_pop($stack) !== $map[$s[$i]]) {
        return false;
      }
    }
  }
  return count($stack) === 0;
}

LeetCode 傳送門 - Valid Parentheses