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;
}

[Oleksii Filonenko]

Rust:

fn valid_curly_braces(input: &str) -> bool {
    let mut counter = 0;
    for c in input.chars() {
        match c {
            '{' => counter += 1,
            '}' => counter -= 1,
            _ => (),
        };
        if counter < 0 {
            return false;
        }
    }
    counter == 0
}

[Alex Khismatulin]

Elegant JS solution

areCurlyBracesMatched = s => {
  while(s.includes('{}')) s = s.replace('{}', '');
  return !s;
}

[Alfredo Salzillo]

I love this one.

[Donald Feury]

Here we Go!... I swear I'm funny sometimes

curly.go

package curly

// Validate will take a string of curly brackets, check it, and determine if it is valid (balanced and in proper order)
// "{}" = true
// "{{}" = false
// "{{}}" = true
func Validate(curlies string) bool {
    if curlies == "" {
        return true
    }

    balanced := 0

    for _, curly := range curlies {
        switch curly {
        case '{':
            balanced++
        case '}':
            balanced--
        }
        if balanced < 0 {
            return false
        }
    }

    return balanced == 0
}

curly_test.go

package curly

import "testing"

var testCases = []struct {
    description string
    input       string
    expected    bool
}{
    {
        "empty string",
        "",
        true,
    },
    {
        "simple string",
        "{}",
        true,
    },
    {
        "incorrect curlies",
        "{{}",
        false,
    },
    {
        "out of order curlies",
        "{}}{",
        false,
    },
    {
        "many curlies",
        "{}{{{}{}}}",
        true,
    },
}

func TestValidate(t *testing.T) {
    for _, test := range testCases {
        if result := Validate(test.input); result != test.expected {
            t.Fatalf("FAIL: %s, Validate(%s): %v - expected %v", test.description, test.input, result, test.expected)
        }
        t.Logf("PASS: %s", test.description)
    }
}

[Amin]

My take at the challenge written in Haskell.

countUnmatchedBraces :: Int -> Char -> Int
countUnmatchedBraces count character
  | character == '{' = count - 1
  | character == '}' = count + 1
  | otherwise = count

unmatchedBraces :: String -> Int
unmatchedBraces = foldl countUnmatchedBraces 0

zero :: Int -> Bool
zero = (==) 0

areCurlyBracesMatched :: String -> Bool
areCurlyBracesMatched = zero . unmatchedBraces


man :: IO ()
main = do
  putStrLn $ show $ areCurlyBracesMatched "const f = a => { console.log(a)" -- False
  putStrLn $ show $ areCurlyBracesMatched "const f = a => { console.log(a) }" -- True
  putStrLn $ show $ areCurlyBracesMatched "const f = a => console.log(a)" -- True

Try it online.

[Rafael Acioly]

Python solution

from collections import Counter


def are_curly_braces_matched(braces: str) -> bool:
    closing_brace = '}'
    opening_brace = '{'

    if braces[0] == closing_brace:
        return False

    elements = Counter(braces)
    return elements.get(opening_brace) == elements.get(closing_brace)