Solving Neetcode 150 problems(Today’s problem :-Valid Parentheses)

Today ,we are going to solve a Valid Parantheses problem.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.

Input: s = "()"
Output: true

Input: s = "(]"
Output: false

A string is considered valid if:

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

You can use a stack data structure to check for the validity of a string. The basic idea is to push an open bracket onto the stack when it is encountered, and pop the top element from the stack when a closing bracket is encountered. If at any point the stack is empty or the top element of the stack does not match the closing bracket, the input string is not valid.

def isValid(s: str) -> bool:
    stack = []
    for c in s:
        if c in "([{":
            stack.append(c)
        elif c in ")]}":
            if not stack:
                return False
            top = stack.pop()
            if c == ")" and top != "(":
                return False
            elif c == "]" and top != "[":
                return False
            elif c == "}" and top != "{":
                return False
    return not stack

Explanation :-

The code is a function in Python called isValid that takes a single argument s, which is the input string containing the characters '(', ')', '{', '}', '[' and ']'. The function returns True if the input string is valid and False otherwise.

The function uses a stack data structure to check the validity of the input string. The basic idea is to push an open bracket onto the stack when it is encountered and pop the top element from the stack when a closing bracket is encountered.

Here is a breakdown of the code:

1. The function starts by initializing an empty stack called stack.
2. The for loop iterates through each character c in the input string s.
3. The first if statement checks if the current character c is an open bracket, i.e., one of "([{", if it is, it appends the character to the stack.
4. The second if statement checks if the current character c is a closing bracket, i.e., one of ")]}".
5. If the character is a closing bracket, the function first checks if the stack is empty by using not stack. If the stack is empty, it means there is no matching open bracket for the current closing bracket, and the function returns False.
6. If the stack is not empty, the function pops the top element from the stack and assigns it to a variable top.
7. The function then checks if the popped element top matches the current closing bracket c. If it does not match, it returns False as the brackets are not closed in the correct order.
8. If the stack is empty after the for loop has finished, it means that all the brackets are closed in the correct order and the function returns True.
9. If the stack is not empty, it means that there are unclosed brackets and the function returns False.

In this way the function checks the string for the conditions mentioned in the problem statement, if the string is valid it returns true else false.

What is it’s Time and Space Complexity?

Time complexity is a measure of how long an algorithm takes to run as a function of the size of the input. Space complexity is a measure of how much memory an algorithm uses as a function of the size of the input.

In this case, the time complexity of the isValid function is O(n), where n is the length of the input string. This is because the function iterates through the input string once, and the push and pop operations on the stack take constant time. The function also uses a single variable top and a single stack, so the space complexity is also O(n).

It’s worth noting that the space complexity is also O(n) , because we use a stack to store the open brackets, and in the worst case, we could have n open brackets in the stack, so we would need n space to store them.

Checkout my GitHub repository here for more coding questions solved :-

GitHub - klaus19/LeetcodeinPython: leetcode problems in python

Happy Coding :)