Brackets

Determine whether a given string of parentheses (multiple types) is properly nested
ℹ️ © Codility, 2009-2018

Problem

A string S consisting of n characters is considered to be “properly nested” if any of the following conditions is true:
• S is empty;
• S has the form “(U)” or “[U]” or “{U}” where U is a properly nested string;
• S has the form “VW” where V and W are properly nested strings.

For example, the string “{[()()]}” is properly nested but “([)()]” is not.

Write a function that, given a string S consisting of n characters, returns 1 if S is properly nested and 0 otherwise.

For example, given S = “{[()()]}”, the function should return 1 and given S = “([)()]”, the function should return 0, as explained above.

Assume that:
• n is an integer within the range [0 … 200,000];
• string S consists only of the following characters: ‘(’, ‘{’, ‘[’, ‘]’, ‘}’ and/or ‘)’.

Complexity:
• expected worst-case time complexity is O(n);
• expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

Solution

C#

using System.Collections.Generic;
class Solution {
  public int solution(string S) {
    Stack<char> T = new Stack<char>();
    foreach (char s in S) {
      if (s == '(' || s == '[' || s == '{') {
        T.Push(s);
      } else {
        if (
          T.Count == 0
          || (s == ')' && T.Peek() != '(')
          || (s == ']' && T.Peek() != '[')
          || (s == '}' && T.Peek() != '{')
        ) {
          return 0;
        }
        T.Pop();
      }
    }
    return T.Count == 0 ? 1 : 0;
  }
}

Java

import java.util.Stack;
class Solution {
  public int solution(String S) {
    Stack<Character> T = new Stack<Character>();
    int n = S.length();
    for (int i = 0; i < n; i++) {
      char s = S.charAt(i);
      if (s == '(' || s == '[' || s == '{') {
        T.push(s);
      } else {
        if (
          T.size() == 0
          || (s == ')' && T.peek() != '(')
          || (s == ']' && T.peek() != '[')
          || (s == '}' && T.peek() != '{')
        ) {
          return 0;
        }
        T.pop();
      }
    }
    return T.size() == 0 ? 1 : 0;
  }
}

JavaScript

function solution(S) {
  let T = [];
  for (i in S) {
    let s = S[i];
    if (s == '(' || s == '[' || s == '{') {
      T.push(s);
    } else {
      if (
        T.length == 0
        || (s == ')' && T[T.length - 1] != '(')
        || (s == ']' && T[T.length - 1] != '[')
        || (s == '}' && T[T.length - 1] != '{')
      ) {
        return 0;
      }
      T.pop();
    }
  }
  return T.length == 0 ? 1 : 0;
}

PHP

function solution($S) {
  $T = [];
  $n = strlen($S);
  for ($i = 0; $i < $n; $i++) {
    $s = $S[$i];
    if ($s == '(' || $s == '[' || $s == '{') {
      array_push($T, $s);
    } else {
      if (
        $m == 0
        || ($s == ')' && $T[count($T) - 1] != '(')
        || ($s == ']' && $T[count($T) - 1] != '[')
        || ($s == '}' && $T[count($T) - 1] != '{')
      ) {
        return 0;
      }
      array_pop($T);
    }
  }
  return count($T) == 0 ? 1 : 0;
}