algoadvance

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.

Clarifying Questions

1. Q: Can the string be empty?
   • A: Yes, the string can be empty. An empty string is considered valid.
2. Q: Are there any characters other than the mentioned brackets in the string?
   • A: No, the string consists only of the characters '(', ')', '{', '}', '[', and ']'.
3. Q: What should be returned if the string is valid?
   • A: Return True if the string is valid, otherwise return False.

Strategy

1. Use a Stack:
   • Use a stack data structure to keep track of the opening brackets.
   • Traverse the string character by character.
   • If the character is an opening bracket ('(', '{', '['), push it onto the stack.
   • If the character is a closing bracket (')', '}', ']'), check if the stack is not empty and whether the top of the stack is the corresponding opening bracket. If so, pop the stack. If not, the string is invalid.
   • Finally, if the stack is empty after traversing the entire string, then all the opening brackets had matching closing brackets in the correct order.

Code

def isValid(s: str) -> bool:
    # Dictionary to match opening and corresponding closing brackets
    matching_bracket = {')': '(', '}': '{', ']': '['}
    
    # Stack to keep track of opening brackets
    stack = []
    
    for char in s:
        if char in matching_bracket.values():  # If it is one of the opening brackets
            stack.append(char)
        elif char in matching_bracket.keys():  # If it is one of the closing brackets
            if stack == [] or stack.pop() != matching_bracket[char]:
                return False
    
    # Check whether the stack is empty (all brackets matched and closed)
    return stack == []

# Example usage
print(isValid("()"))       # Output: True
print(isValid("()[]{}"))   # Output: True
print(isValid("(]"))       # Output: False
print(isValid("([)]"))     # Output: False
print(isValid("{[]}"))     # Output: True

Time Complexity

• Time Complexity: O(n) where n is the length of the string s. Each character is processed once, either pushed onto the stack or matched and popped.
• Space Complexity: O(n) in the worst case, if all the characters in the string are opening brackets, they will all be pushed onto the stack.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?