Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Balanced Parentheses

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

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

Anonymous

· 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
}
A

Anonymous

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

Anonymous

· 2 years ago

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

A

Anonymous

· 3 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

Reading Progress

0%

Vote for new content