# Valid Parentheses#

## Intro#

In the comments, people say this problem should bin in the 6kyu category.

Example input and output:

validParens ""                → True
validParens "("               → False
validParens "(("              → False
validParens ")(()))"          → False
validParens "()"              → True
validParens "()()"            → True
validParens "((()))"          → True
validParens "())()("          → False
validParens "(())((()())())"  → True


### v1#

{-# LANGUAGE NoMonomorphismRestriction #-}

incIf :: Char -> Char -> Int -> Int
incIf c1 c2 n
| c1 == c2 = (+ 1) n
| otherwise = n

validParens :: String -> Bool
validParens str = go str 0 0
where
go :: String -> Int -> Int -> Bool
go s l r
| length s == 0 = l == r
| r > l = False
| otherwise = go
(tail s)


### v2#

Saw this example from another user’s solution. Not how I would do it, but I was curious on how it worked.

validParens :: String -> Bool
validParens = (== 0) . foldr
(\c n ->
if n < 0
then n
else
if c == ')'
then n + 1
else n - 1) 0


### v3#

{-# LANGUAGE NoMonomorphismRestriction #-}

incIf :: Char -> Char -> Int -> Int
incIf c1 c2 n
| c1 == c2 = (+ 1) n
| otherwise = n

--
-- In go, instead of checking if the length is 0 and then using head and
-- tail later, consider pattern matching instead (which also allows GHC
-- to warn you about missing patterns).
--
validParens :: String -> Bool
validParens str = go str 0 0
where
go :: String -> Int -> Int -> Bool
go [] l r = l == r
go (h : t) l r
| r > l = False
| otherwise = go
t
(incIf h '(' l)
(incIf h ')' r)


## JavaScript#

### v1#

/**
* Recursive solution using the run/go helper function approach.
*
* - T.C: O(n).
* - S.C: O(n).
*
* @param {string}
* @returns {number}
*/
function validParens(s) {
return (function go(lst, l, r) {
if (lst.length === 0) return l === r;

if (lst[0] === '(') ++l;
if (lst[0] === ')') ++r;

if (r > l) return false;

return go(lst.slice(1), l, r);
})([...s], 0, 0);
}


### v2#

/**
* @param {string}
* @returns {number}
*/
function validParens(s) {
return (function go(l, c) {
if (l.length === 0) return c === 0;

if (l[0] === '(') ++c;
if (l[0] === ')') --c;

if (c < 0) return false;

return go(l.slice(1), c);
})([...s], 0);
}