Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Problem 1: Balanced Parentheses (easy)

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!
R

rahul.dhammy

· 2 years ago

We dont need to iterate the entire string we can return false as soon as we first find the mismatched braces. This means we dont need to check the length of the stack at the end. Please see my solution below:

public bool isValid(string s) {
        
        if(s.Length==1) // One char string for sure would not be balanced
            return false;
            
        Dictionary<char,char> closingOpeningBracesPairMap = new Dictionary<char,char>();
        closingOpeningBracesPairMap.Add(')','(');
        closingOpeningBracesPairMap.Add(']','[');
        closingOpeningBracesPairMap.Add('}','{');

        Stack<char> stack = new Stack<char>();
      
        for(int i = 0; i < s.Length; i++)
        {
            if(IsOpeningBrace(s[i]))
            {
                stack.P
Show 2 replies