Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Balanced Parentheses

Problem Statement

Given a string s containing (, ), [, ], {, and } characters. Determine if a given string of parentheses is balanced.

A string of parentheses is considered balanced if every opening parenthesis has a corresponding closing parenthesis in the correct order.

Example 1:

Input: String s = "{[()]}";
Expected Output: true
Explanation: The parentheses in this string are perfectly balanced. Every opening parenthesis '{', '[', '(' has a corresponding closing parenthesis '}', ']', ')' in the correct order.

Example 2:

.....

.....

.....

Like the course? Get enrolled and start learning!
E

egor_grud

· a year ago

#include <iostream>
#include <stack>
#include <map>
using namespace std;

class Solution
{
    static const inline map<char, char> parenparenthesises = {
        { ')', '(' },
        { '}', '{' },
        { ']', '[' }
    };
public:
    bool isValid(string s)
    {
        stack<char> nested_braces;
        for (const char ch : s)
        {
            auto it = parenparenthesises.find(ch);
            if (it == parenparenthesises.end())
            {
                nested_braces.push(ch);
            }
            else if (!nested_braces.empty() && ch == it->first && nested_braces.top() == it->second)
            {
                nested_braces.pop();
            }
            else
            {
                return false;
            }
        }

        return nested_b