Post

# Valid Parentheses

• 25.8k
• 0
• 1

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

Recommended Free Ebook
Similar Articles