17 - Valid Parentheses

Don't say so much, just coding...

Instruction

Write a function called that takes a string of parentheses, and determines if the order of the parentheses is valid. The function should return true if the string is valid, and false if it's invalid.

Examples

  "()"              =>  true
  ")(()))"          =>  false
  "("               =>  false
  "(())((()())())"  =>  true

Constraints

0 <= input.length <= 100

Along with opening (() and closing ()) parenthesis, input may contain any valid ASCII characters. Furthermore, the input string may be empty and/or not contain any parentheses at all. Do not treat other forms of brackets as parentheses (e.g. [], {}, <>).

Ruby

Init

  def valid_parentheses(string)
    #your code here
  end

Sample Testing

  Test.assert_equals(valid_parentheses("  ("),false)
  Test.assert_equals(valid_parentheses(")test"),false)
  Test.assert_equals(valid_parentheses(""),true)
  Test.assert_equals(valid_parentheses("hi())("),false)
  Test.assert_equals(valid_parentheses("hi(hi)()"),true)

Javascript

Init

  function validParentheses(parens){
    //TODO 
  }

Sample Testing

  Test.assertEquals(validParentheses( "()" ), true);
  Test.assertEquals(validParentheses( "())" ), false);

Thinking

想法(1): 唯有先左括弧 ( 再配上 ) 才可以有機會回傳 true，反之先 ) 再左 ( 還是應該回傳 false

圖片來源：Unsplash Thought Catalog

Hint & Reference

• Ruby
  • Ruby - apidock Zero?
• JavaScript
  • JS - MDN Array.prototype.includes()

Solution

Ruby

  # Solution 1
  def valid_parentheses(string)
    count = 0
    string.chars.each do |char|
      count += 1 if char == "("
      count -= 1 if char == ")"
      return false if count < 0
    end
    count.zero?
  end

Javascript

  // Solution 1
  function validParentheses(parens){
  var count = 0;
    for (var i = 0; i < parens.length; i++) {
      if (parens[i] === '(') count++;
      if (parens[i] === ')') count--;
      if (count < 0) return false;
    }
    
    return count === 0;
  }
  
  // Solution 2
  function validParentheses(parens){
    while(parens.includes("()")){
      parens = parens.replace("()", "")
    }
    
    return (parens === "") ? true : false
  }