Post
Ask Question

Valid Parentheses

I came from science, I have never had a chance to learn or play a game such as an algorithm in my student career. Most algorithm problems I met are in interviews. In my view, these kinds of tricks are just boby level games, but if you did not have related training previously, you might not get the solution immediately. So, I will open a topic, or series, to record the algorithm questions I met or I played previously (10/03/2021, from my first algorithm article).

This series will include,

I will add more on this topic probably from my notes or practice code.

Introduction

This is the structure of this article,

  • Introduction
  • A - Question
  • B - Initial Solution
  • C - Good Solution

A - Question

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if,

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Example 1

Input: s = "()"
Output: true

Example 2

Input: s = "()[]{}"
Output: true

Example 3

Input: s = "(]"
Output: false

Example 4

Input: s = "([)]"
Output: false

Example 5

Input: s = "{[]}"
Output: true

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

B - Initial Solution

public class ValidParentheses {
    public bool Valid(String s) {
        Stack left = new Stack();
        foreach(char c in s.ToCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                left.Push(c); // Get left
            }
            // Compare to right:
            else if (c == ')' && left.Count != 0 && (char) left.Peek() == '(') {
                left.Pop();
            } else if (c == '}' && left.Count != 0 && (char) left.Peek() == '{') {
                left.Pop();
            } else if (c == ']' && left.Count != 0 && (char) left.Peek() == '[') {
                left.Pop();
            } else {
                return false; // no match
            }
        }
        return true;
    }
}

Main Program

static void Main(string[] args) {
    ValidParentheses validParentheses = new ValidParentheses();
    string input = "()";
    Console.WriteLine(validParentheses.Valid("()")); // true
    Console.WriteLine(validParentheses.Valid("()[]{}")); // true
    Console.WriteLine(validParentheses.Valid("(]")); // false
    Console.WriteLine(validParentheses.Valid("([)]")); // false
    Console.WriteLine(validParentheses.Valid("{[]}")); // true
    Console.WriteLine();
}

Results

//Example 1:
//Input: s = "()"
//Output: true
//Example 2:
//Input: s = "()[]{}"
//Output: true
//Example 3:
//Input: s = "(]"
//Output: false
//Example 4:
//Input: s = "([)]"
//Output: false
//Example 5:
//Input: s = "{[]}"
//Output: true

This solution is logically correct, but it is not efficient. It cannot pass HackerRank test or LeetCode test.

C - Accepted Solution

public class ValidParentheses {
    public bool Valid(String s) {
        int n = -1;
        while (s.Length != n) {
            n = s.Length;
            s = s.Replace("()", "");
            s = s.Replace("{}", "");
            s = s.Replace("[]", "");
        }
        if (s.Length == 0) return true;
        else return false;
    }
}

Reference


Similar Articles