'Valid Braces - CodeWars Challenge

There is a challenge on codewars that asks you to check whether a string of parentheses, brackets, and curly braces is valid.

A string of braces is considered valid if all braces are matched with the correct brace.

I.e. "()" is valid and "[(])" is not.

"(){}[]" is valid and "[({})](]" is not. Etc.

I've been able to create some logic to check for whether or not there are the right number of opening and closing braces.

ATTEMPT:

function validBraces(braces) {

  let parenCount = 0;
  let squareBracketCount = 0;
  let curlyBraceCount = 0;

    for (let i =0; i < braces.length; i++) {
      let character = braces[i];
        if (character === "(") {
          parenCount -= 1;
          }
        if (character === ")") {
          parenCount += 1;
          }
        if (character === "[") {
          squareBracketCount -= 1;
          }
        if (character === "]") {
          squareBracketCount += 1;
        }
        if (character === "{") {
          curlyBraceCount -= 1;
        }
        if (character === "}") {
          curlyBraceCount += 1;
        }
      }
      if (parenCount === 0 && squareBracketCount === 0 && curlyBraceCount === 0) {
        return true;
      } 
      else {
        return false;
      }
}

But I've not been able to come up with a way to check for whether or not the opening brace "closes" before the next type of brace opens.

Maybe something like this?

if (
  (firstChar === "(" && lastChar === ")") ||
  (firstChar === "{" && lastChar === "}") ||
  (firstChar === "[" && lastChar === "]")
) {
  return true;
} else {
  return false;
}

But then this would have to be checked in accordance with my other if-statement...(?)

EDIT: Key to understanding this challenge is that the closing brace must either come directly after the opening brace or it must be "parallel" - in symmetry with the other.

Solution 1:^[1]

You can use array to keep track of previously appeared opening braces and once any closing tag appears you need to match it with the last value of array if it's matching pop the last value out of else else return false, in the end if you're left with empty array return true else return false

function validBraces(braces){
  let tracer = []
  for(let i=0;i < braces.length; i++){
    if ( braces[i] === "(" || braces[i] === "{" || braces[i] === "["){
      tracer.push(braces[i])
    } else{
      if(tracer.length === 0) return false
      let lastValue = tracer[tracer.length-1]
      if( (braces[i] === ']' && lastValue === '[') || (braces[i] === '}' && lastValue === '{') || (braces[i] === ')' && lastValue === '('))
      {
        tracer.pop()
      } else {
        break;
      }
    }
  }
  return tracer.length === 0
}


console.log(validBraces( "()" )) // true
console.log(validBraces( "[]" )) // true
console.log(validBraces( "{}" )) // true
console.log(validBraces( "(){}[]" )) // true
console.log(validBraces( "([{}])" )) // true
console.log(validBraces( "(}" )) // false
console.log(validBraces( "[(])" )) // false
console.log(validBraces( "({})[({})]" )) // true
console.log(validBraces( "(})" )) // false
console.log(validBraces( "(({{[[]]}}))" )) //true
console.log(validBraces( "{}({})[]" )) // true
console.log(validBraces( ")(}{][" )) // false
console.log(validBraces( "())({}}{()][][" )) // false
console.log(validBraces( "(((({{" ))  // false
console.log(validBraces( "}}]]))}])" )) // false

Solution 2:^[2]

You don't really need to use arrays here, you can just use regex and recursion:

const regex = /\(\)|\[\]|\{\}/;
const validBraces = braces => regex.test(braces)
  ? validBraces(braces.replace(regex, ''))
  : '' === braces

console.log(validBraces('{{}}')) // true
console.log(validBraces('{{[]}}')) // true
console.log(validBraces('{[{}]}')) // true
console.log(validBraces('({{}})')) // true
console.log(validBraces('{[()]}')) // true
console.log(validBraces('{{}[}')) // false
console.log(validBraces('{{]}}')) // false
console.log(validBraces('{}}')) // false
console.log(validBraces('{({}}')) // false
console.log(validBraces('((}}')) // false
console.log(validBraces('}[)}')) // false

Solution 3:^[3]

In scala you can do this

object Kata {

  def validBraces(s: String): Boolean =
    s.replace("()", "").replace("[]", "").replace("{}", "") match { case "" => true; case `s` => false; case x => validBraces(x) }
}

Solution 4:^[4]

function validBraces(braces){
 while(/\(\)|\[\]|\{\}/g.test(braces)){braces = braces.replace(/\(\)|\[\]|\{\}/g,"")}
 return !braces.length;
}

// double regex

Solution 5:^[5]

I have done it in Scala with some tests and it works. In case the string's length is 2 if dont need to enter the recursive call because in the match you have already checked if it correct or not :

   object Kata1{
        def validBraces(s: String): Boolean ={
          var valid: Boolean = true
          if(s.length > 1){
           s(0) match{
              case '('  => if( s(1) == ')' || s(s.length-1) == ')'){
                if(s.length != 2){
                  if(s(1) == ')'){
                    valid = validBraces(s.substring(2, s.length))
                  }else{
                    valid = validBraces(s.substring(1, s.length-1))
                  }
                }
          } else {
                if(s.lastIndexOf(')') != -1){
                 var newS = s.substring(0, s.indexOf(')')).concat(s.substring(s.indexOf(')')+1, s.length))
                  valid = validBraces(newS.substring(1, s.length-1))
                }else valid = false
           }
        case '['  => if( s(1) == ']' || s(s.length-1) == ']') {
         if(s.length != 2){
          if(s(1) == ']'){
           valid = validBraces(s.substring(2, s.length))
         }else{
           valid = validBraces(s.substring(1, s.length-1))
         }
       }
      } else {
       if(s.lastIndexOf(']') != -1){
         var newS = s.substring(0, s.indexOf(']')).concat(s.substring(s.indexOf(']')+1, s.length))
        valid = validBraces(newS.substring(1, s.length-1))
      }else valid = false
    }
    case '{'  => if( s(1) == '}' || s(s.length-1) == '}') {
      if(s.length != 2){
        if(s(1) == '}'){
          valid = validBraces(s.substring(2, s.length))
        }else{
          valid = validBraces(s.substring(1, s.length-1))
        }
      }
    } else {
      if(s.lastIndexOf('}') != -1){
        var newS = s.substring(0, s.indexOf('}')).concat(s.substring(s.indexOf('}')+1, s.length))
        valid = validBraces(newS.substring(1, s.length-1))
      }else valid = false
    }
    case _ => valid = false
  }
  /*if(s.length != 2 && valid){
    if(s(1) == ')'  || s(1) == '}'  || s(1) == ']' ){
      valid = validBraces(s.substring(2, s.length))
    }else{
      valid = validBraces(s.substring(1, s.length-1))
    }
  }*/
}else{
  valid = false
}

if(s.length == 0){
  valid = true
}
valid
 }
 }

 Kata1.validBraces("()") //true
 Kata1.validBraces("[()]") //true
 Kata1.validBraces("[(])") //false
 Kata1.validBraces("([{}])") //true
 Kata1.validBraces("([{]})") //false
 Kata1.validBraces("{({{()}({}())})}")//true
 Kata1.validBraces("({]}{")//false

Solution 6:^[6]

My JavaScript solution of this kata is simple to understand and passes all tests. Yet im aware its optimization isn't top-notch. It simply eliminates elements step by step:

Start: ( { [] } ) || ( { [] } }
Then: ( {} ) || ( {} }
Then: () || (} Finish: clear || leftovers
When length = 0 it passes, and when length > 0 it wont

   function validBraces(braces){
while(braces.indexOf("{}") !== -1 || braces.indexOf("()") !== -1 || braces.indexOf("[]") !== -1){
    braces = braces.replace("{}", "").replace("()", "").replace("[]", "");
}
return braces.length === 0 ? true: false;

console.log(validBraces("(({{[[]]}}))"));

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution	Source
Solution 1
Solution 2	Mike K
Solution 3	ravi malhotra
Solution 4	General Grievance
Solution 5
Solution 6

'Valid Braces - CodeWars Challenge

Solution 1:[1]

Solution 2:[2]

Solution 3:[3]

Solution 4:[4]

Solution 5:[5]

Solution 6:[6]