Grokking the Engineering Manager Coding Interview

0% completed

​

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

Adrian Adewunmi

· 2 years ago

Hi,

Referring to Problem 1's (Balanced Parentheses) solution - line 16, which method is more appropriate for testing for an empty stack - isEmpty() or empty()?

if (stack.isEmpty()) {
    return false;
}
OR
if (stack.empty()) {
    return false;
}
Show 2 replies
Andre Abtahi

Andre Abtahi

· 2 years ago

The constraint says s.length can be at minimum size 1. But one of the inputs was an empty string....

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
F

fellainthewagon

· 2 years ago

type Solution struct{}

func (s *Solution) isValid(str string) bool {
  par := map[byte]byte{
    '[': ']',
    '(': ')',
    '{': '}',
  }

  stack := []byte{}

  for i := 0; i < len(str); i++ {
    curr := str[i]

    if v, ok := par[curr]; ok {
      // if curr is opening push its closing to stack
      stack = append(stack, v)
    } else if len(stack) != 0 && curr == stack[len(stack)-1] {
      // otherwise curr should be correct closing - so pop it from stack
      stack = stack[:len(stack)-1]
    } else {
      // in that case curr is incorrect closing
      return false
    }
  }
  
  return len(stack) == 0
}
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
    def isValid(self, s):
        stack = []
        for char in s: 
            if char == '{' or char == '[' or char == '(':
                stack.append(char)
            else:
                popped = stack.pop()
                if popped == '{' and char != '}':
                    return False
                elif popped == '[' and char != ']':
                    return False
                elif popped == '(' and char != ')':
                    return False
                   
        return len(stack) == 0
Show 1 reply
Enrique Fernández

Enrique Fernández

· 2 years ago

class Solution:
    def isValid(self, s):
        # ToDo: Write Your Code Here.
        stack = []
        parentheses = {")": "(" , "]": "[" ,  "}" : "{"}
        if len(s) % 2 != 0:
            return False
        for c in s:
            if c not in parentheses.keys():
                stack.append(c)
            elif stack:
                top = stack.pop(-1)
                if top != parentheses[c]:
                    return False 
            else:
                return False
                    
        return True
Andrew Sologor

Andrew Sologor

· a year ago

func isValid(s1 string) bool {
    stack := []rune{}

    for _, c := range s1 {
        switch c {
        case '(':
            stack = append(stack, ')')
        case '[':
            stack = append(stack, ']')
        case '{':
            stack = append(stack, '}')
        case ')', ']', '}':
            if len(stack) == 0 || stack[len(stack) - 1] != c {
                return false
            }
            
            // remove the last element from the stack
	          stack = stack[:len(stack) - 1]
        }
    }

    return len(stack) == 0
}
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
Subham Choudhury

Subham Choudhury

· a month ago

Solution import java.util.Stack;

public class Solution {     public boolean isValid(String s) {         Stack<Character> stack = new Stack<>();         for(Character c : s.toCharArray()){             if(c=='{' ||c=='('||c=='['){                 stack.push(c);             }else{                 if(stack.isEmpty()) return false;                 Character top = stack.pop();                 if (c == '}' && top != '{') return false;                 if (c == ']' && top != '[') return false;                 if (c == ')' && top != '(') return false;             }         }         return stack.isEmpty();     } }