LeetCode Js-20. Valid Parentheses

    AllenLi
    LeetCode Js-Array

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

    給予指定的符號，確認是否有效。('()', '{}', '[]')

    Example 1:

    Input: s = "()"
Output: true

    Example 2:

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

    Example 2:

    Input: s = "(]"
Output: false

    Solution:
    1. 運用「for…of」將input進行迴圈，比對錯誤即回傳false
    2. 當「if條件」符合左括號時，push()放入空陣列中
    3. 當「if條件」出現右括號時，pop()比對上一次儲存的左括號
    4. 最後當宣告的空陣列長度為0時，回傳ture

    Code 1: BigO(n)

    var isValid = function(s) {
    const array: string[] = []
    const map: Record = {
        ")":"(",
        "]":"[",
        "}":"{"
    }

    for (let char of s) {
        if (char === "(" || char === "[" || char === "{") {
            array.push(char)
        } else if (array.pop() !== map[char]) {
            return false;
        }
    }
    return (array.length === 0)
};

    FlowChart:
    Example 1

    step.1
char = '('
array = [] => array = ['(']

step.2
char = ')'
array.pop = ['('] => map[char] = ['(']
array.length === 0 => true

    Example 2

    step.1
char = '('
array = [] => array = ['(']

step.2
char = ')'
array.pop = ['('] => map[char] = ['(']

step.3
char = '['
array = [] => array = ['[']

step.4
char = ']'
array.pop = ['['] => map[char] = [']']

step.5
char = '{'
array = [] => array = ['[']

step.6
char = '}'
array.pop = ['{'] => map[char] = ['{']
array.length === 0 => true

    Example 3

    step.1
char = '('
array = [] => array = ['(']

step.2
char = '}'
array.pop = ['('] => map[char] = ['{']
return false

    Code 2: BigO(n)

    var isValid = function(s) {
  const array: string[] = []

  for (i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      array.push(')')
    } else if (s[i] === '{') {
      array.push('}')
    } else if (s[i] === '[') {
      array.push(']')
    } else if (array.pop() !== s[i]) {
      return false;
    }
  }
  return (array.length === 0);
};

    Related Posts