Checking balanced brackets using stacks

-
Hi, today's problem is a relatively common one in technical interviews, here it is from Daily Coding Problem:

This problem was asked by Facebook.
Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string "([])[]({})", you should return true.
Given the string "([)]" or "((()", you should return false.

Here is the approach:
 - First have a hash table which you can use to (quickly) map an open bracket to a closed bracket. You can also use it as an open bracket checker
 - Then use a standard stack. Push open brackets. Pop closed ones, check for matches.
 - Stack should be empty at the end

That's it, code is on Github https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProblem10112018.cs and below, thanks, Boris
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace DailyCodingProblem
{
 class DailyCodingProblem10112018
 {
  public bool BracketsBalanced(string str)
  {
   if (String.IsNullOrEmpty(str)) return true;

   string b = "(){}[]";
   Hashtable brackets = new Hashtable();
   for (int i = 0; i < b.Length; i += 2) brackets.Add(b[i], b[i + 1]);

   Stack stack = new Stack();

   for (int i = 0; i < str.Length; i++)
   {
    if (brackets.ContainsKey(str[i])) stack.Push(str[i]);
    else
    {
     if (stack.Count == 0) return false;
     char c = stack.Pop();
     if (!brackets.ContainsKey(c) || (char)brackets[c] != str[i]) return false;
    }
   }
   return stack.Count() == 0;
  }
 }
}

Comments

  1. TarasDecember 31, 2018 at 9:04 PM

    Very nice! This problem is also available on leetcode - https://leetcode.com/problems/valid-parentheses. Smart compilers are actually able to generate more efficient lookup tables for switches and in some languages the implementation is fairly concise. For example my Rust implementation defines a match_of lookup function that is based on pattern matching (fancy switch):

    impl Solution {
    pub fn is_valid(s: String) -> bool {
    let mut stack = Vec::new();
    let match_of = |c: char| -> char {
    match c {
    ')' => '(',
    '}' => '{',
    ']' => '[',
    _ => panic!("Invalid closing bracket"),
    }
    };
    for ch in s.chars() {
    match ch {
    '(' | '{' | '[' => stack.push(ch),
    closing => {
    if let Some(closing_bracket) = stack.pop() {
    if closing_bracket != match_of(closing) {
    return false;
    }
    } else {
    return false;
    }
    }
    }
    }
    stack.is_empty()
    }
    }

    https://gist.github.com/ttsugriy/3dc568c9e55b90233849090707f065b3

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more