20. Valid Parentheses

Question Type: Easy
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.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input:

"()"

Output:

 true

Example 2:

Input:

"()[]{}"

Output:

true

Example 3:

Input:

"(]"

Output:

false

Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

Approach:

To solve this problem, we can use a stack data structure. The idea is to iterate through the input string character by character and:

1. If we encounter an opening bracket ('(', '{', '['), we push it onto the stack.

2. If we encounter a closing bracket (')', '}', ']'), we check if the stack is empty. If it is, we return false because there is no corresponding opening bracket to match the current closing bracket.

3. If the stack is not empty, we pop the top element from the stack and check if it matches the current closing bracket. If they do not match, we return false because the brackets are not in the correct order.

4. After processing all characters, if there are any remaining elements in the stack, it means there are unmatched opening brackets, so we return false.

5. If the stack is empty after processing all characters, we return true, indicating that the input string is valid.

6. This approach ensures that open brackets are closed in the correct order, and it also handles cases where the input string contains only opening brackets or only closing brackets.

Code:

class Solution {
    public boolean isValid(String s) {
    //    using stack 

        Stack<Character> stack = new Stack<>();

        for(char ch: s.toCharArray()){
            switch(ch){
                case '(':
                case '{':
                case '[':
                    stack.push(ch);
                    break;
                case ')':
                    if(stack.isEmpty() || stack.pop() != '('){
                        return false;
                    }
                    break;
                case'}':
                    if(stack.isEmpty() || stack.pop() != '{'){
                        return false;
                     }
                     break;
                case ']':
                    if(stack.isEmpty() || stack.pop() != '['){
                        return false;
                    }
                    break;


            }
        }

        return stack.isEmpty();
    }
}

Why this Approach?

1. The stack-based approach ensures that opening brackets are matched with their corresponding closing brackets, maintaining the correct order.

2. It efficiently handles edge cases with unmatched brackets and allows for early detection of invalid strings.

3. This approach's simplicity and linear time complexity make it an optimal solution for determining the validity of parentheses in a given string.

Happy coding,
shiva