Daily Challenge #51 - Valid Curly Braces

Challenge
Write a function areCurlyBracesMatched that takes in a string s containing only { and/or } and returns true if s is properly matched, and false otherwise.

A string s is considered properly matched if the string is empty or if every open brace has a corresponding close brace.

Examples
{{}} is properly matched.
{{{ is not properly matched.
{}{}{} is properly matched.

areCurlyBracesMatched("{{{}{}}}"), true;
areCurlyBracesMatched("{{"), false;
areCurlyBracesMatched("{}}"), false;
areCurlyBracesMatched(""), true;

Happy coding!

---

This challenge comes from theonlydaryl on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[Mat-R-Such]

Python

import re
def areCurlyBracesMatched(s):
    if len(re.findall('[^{}]',s)) > 0 : return False
    while True:
        start = s.find('{')
        end = s.find('}')
        if start < end and (start >=0 and end >= 0):
            s=s.replace('{','',1)
            s=s.replace('}','',1)
        else:
            break
    if len(s) == 0: return True
    else:   return False

[K.V.Harish]

My solution in js

const areCurlyBracesMatched = (str) => {
  let counter = 0;
  str.split('').every((brace) => !((counter = brace === '{' ? counter+1 : counter-1) < 0));
  return !counter;
}; 

[DeLiXx]

Simple JS solution

Iterate through the string and count up when you encounter a "{" and down when not.
Check after every iteration, if the last character was a closing brace too much and return false if so.
Finally, return true when the amount of opening braces matches the amount of closing braces (i == 0).

function areCurlyBracesMatched(s){
    i = 0;
    for (el of s){
    i += "{" == el ? 1 : -1;
        if (i < 0) return false;
    }
    return !i
};

[Josh]

Ahh, this old trick. I've done it for at least two interviewers this summer. Terrific way for them to determine how good I am at building Rails applications, but, I digress.

def balanced?(string, left, right)
  raise ArgumentError.new("Can't compare individual characters to a character sequence") if left.length >1 || right.length > 1
  string.chars.reduce(0) do |count, char|
    return false if count < 0
    count += 1 if char == left
    count -= 1 if char == right
  end.zero?
end

def areCurlyBracesMatched(string)
  balanced?(string, "{", "}")
end

[Ganesh Prasad]

Functional JS with Tail Call Optimization (TCO)

const test = require('./tester');

const validateTCO = (acc, str) => (
    typeof str !== 'string'     ? false
    : str.length === 0          ? acc === 0
    : str.charAt(0) === '{'     ? validateTCO (acc + 1, str.slice(1))
    : str.charAt(0) === '}'     ? validateTCO (acc - 1, str.slice(1))
    : validateTCO (acc, str.slice(1))
);

const validate = str => validateTCO (0, str);

test (validate, [
    {
        in: ['{{}}'],
        out: true,
    },
    {
        in: ['{{{'],
        out: false,
    },
    {
        in: ['{}{}{}'],
        out: true,
    },
    {
        in: ['{abc {def} {{}}}'],
        out: true,
    },
]);

[Olek Ria]

Some F#

let rec areCurlyBracesMatched (x:string) =
    match "{}" |> x.IndexOf with
    | -1 ->  x.Length = 0
    | _  ->  x.Replace("{}", "") |> areCurlyBracesMatched

[E. Choroba]

Perl solution.

Just remove all the {}s until there's nothing to remove. If you got an empty string, the input was valid.

#!/usr/bin/perl
use warnings;
use strict;

sub are_curly_braces_matched {
    my ($s) = @_;
    1 while $s =~ s/{}//g;
    return ! length $s
}

use Test::More tests => 4;

ok are_curly_braces_matched('{{{}{}}}');
ok ! are_curly_braces_matched('{{');
ok ! are_curly_braces_matched('{}}');
ok are_curly_braces_matched("");

[Xavier Dubois 🇫🇷]

Damn, there is never any PHP solutions, I've to get to it !

[Olivier “Ölbaum” Scherler]

With the examples given, this challenge is identical to Challenge 29: Xs and Os, because counting the braces suffice to get the answer.

If you add areCurlyBracesMatched("}{"), false;, though, it’s different.

I think it’s a pity that the examples for a lot of these challenges are missing some important cases that would help when the explanation is not completely clear.

[Kilian]

Let's see what you guys think...

C++

#include <iostream>
#include <stack>
#include <string>

bool isValidCurlyBraceExpression(std::string expressionToCheck);

void test(std::string expression, bool expectation);

int main(int argc, char* argv[])
{
    test("{{{}{}}}", true);
    test("{{", false);
    test("{}}", false);
    test("}{", false);
    test("", true);
    return 0;
}

void test(std::string expression, bool expectation){
    bool returnValue = isValidCurlyBraceExpression(expression);
    if(returnValue == expectation)
        std::cout << "Test succeeded \"" << expression << "\" = " << returnValue << std::endl;
    else
        std::cerr << "Test failed!   \"" << expression << "\" = " << returnValue << std::endl;
}

bool isValidCurlyBraceExpression(std::string expressionToCheck)
{
    std::stack<char> openedBraces;
    for (auto it = expressionToCheck.begin(); it != expressionToCheck.end(); ++it) {
        if (*it == '{') {
            openedBraces.push('{');
        }
        else if (*it == '}') {
            if (openedBraces.empty())
                return false;
            openedBraces.pop();
        }
    }
    if (openedBraces.empty())
        return true;
    else
        return false;
}