見習村17 - Valid Parentheses

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

1
2
3
4
"()"              =>  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

1
2
3
def valid_parentheses(string)
  #your code here
end

Sample Testing

1
2
3
4
5
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

1
2
3
function validParentheses(parens){
  //TODO 
}

Sample Testing

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

Thinking

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

https://ithelp.ithome.com.tw/upload/images/20201002/20120826gDzqXRaQ1t.jpg
圖片來源：Unsplash Thought Catalog

Hint & Reference

Solution

Ruby

1
2
3
4
5
6
7
8
9
10
# 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 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
}