Understand Valid Parenthesis Problem

Problem Name: Valid Parenthesis
Problem Description:

Problem: Valid Parentheses

Difficulty: Easy
Topics: Strings, Stack, Algorithms
Companies: Relevant for interviews at top tech companies.

Problem Description

You are given a string s containing only the characters '(', ')', '{', '}', '[', and ']'. Your task is to determine whether the input string is valid.

Validity Criteria

A string is considered valid if:

  • Matching Brackets: Open brackets are closed by the same type of brackets.
  • Correct Order: Open brackets are closed in the correct order.
  • Balanced Brackets: Every closing bracket has a corresponding open bracket of the same type.

Input Format

A single string s consisting of the characters '(', ')', '{', '}', '[', and ']'.

Constraints

  • 1 <= s.length <= 10⁴
  • The string contains only the characters: '(', ')', '{', '}', '[', and ']'.

Output Format

Return true if the input string is valid.
Return false otherwise.

Examples

Example 1:

Input:
s = "()"
Output:
true

Example 2:

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

Example 3:

Input:
s = "(]"
Output:
false

Example 4:

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

Hints

  • Use a stack to keep track of open brackets.
  • Traverse the string character by character:
    • Push open brackets onto the stack.
    • When encountering a closing bracket, check if the top of the stack matches its corresponding open bracket.
    • If the stack is empty at the end of traversal, the string is valid. Otherwise, it is invalid.
Category:
  • 2D Arrays
Programming Language:
  • Java
Reference Link:

https://leetcode.com/problems/valid-parentheses/description/

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
Main Function is not defined.
Helper Function:
input: "{}()[]"
Output: True
public static void isValid(string s){
stack <char>sk;
for(int i = 0; i< s.length();i++)
if(s[i] == '(' || s[i] == '{' || s[i] == '['){
sk.push(s[i]);
}
else{
if(s[i] == ')' || s[i] == ')' || s[i] == ')'){
if(sk.size() == 0){
return false;
}
else{
if(sk.top() != '(' && s[i] == ')' )){
return false;
}
else{
if(sk.top() != '{' && s[i] == '}' ){
return false;
}
else{
if(sk.top() != '[' && s[i] == ']' ){
return false;
}
else{
sk.pop();
}
}
}
}
}
}
for loop end
if(sk.size() == 0){
return true;
}
else{
return false;
}
}//function end
Utility Functions and Global variables:
Utility Function is not required.
Privacy Policy | About