Decoding Parentheses Matching: PHP Edition

Introduction

In this post, we’ll delve into a PHP function that efficiently determines whether the parenthesis in a given string are properly matched or not.

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

Exploring Code

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
       $opentoclose = ["("=>")", "{"=>"}","["=>"]"];
       $closetoopen = array_flip($opentoclose);
       $stack = [];

       for($i=0; $i<strlen($s); $i++) {
            $char = $s[$i];
            if (array_key_exists($char, $opentoclose)) {
                array_push($stack,$char);
            } else {
                if (count($stack) === 0) {
                    return false;
                } else if ($closetoopen[$char] === end($stack)) {
                    array_pop($stack);
                } else {
                    return false; 
                }
            }
        }
        return empty($stack);
    }
}

Explanation

1. Symbol Mapping: The function initializes an array $opentoclose to map opening symbols to their corresponding closing symbols. Another array $closetoopen is created by flipping the keys and values of $opentoclose, making it easier to check closing symbols against their opening counterparts.
2. Stack: It uses a stack to keep track of opening symbols encountered. PHP arrays can be used as stacks using functions like array_push() and array_pop().
3. Iteration: The function iterates through each character in the input string.
4. Symbol Handling:

• If the character is an opening symbol, it’s pushed onto the stack.
• If it’s a closing symbol:
  - If the stack is empty, indicating a mismatch, the function returns false.
  - If the closing symbol matches the last opening symbol on the stack, the last opening symbol is popped from the stack.

5. Completion: After iterating through the string, if the stack is empty, it means all opening symbols have been matched with closing symbols, and the function returns true. Otherwise, it returns false.

Space and Time Complexity

The time complexity of the provided isValid() function is O(n), where n is the length of the input string. This is because the function iterates through each character of the string once.

Let’s break down the operations:

• Iterating through the string: O(n) where n is the length of the string.
• Pushing and popping elements from the stack: These operations have a time complexity of O(1) because they involve adding or removing elements from the end of the array, which can be done in constant time.

Hence, the overall time complexity is O(n).

The space complexity of the function is also O(n) because in the worst case, the stack could contain all opening parenthesis symbols from the input string.

Conclusion

The provided PHP function efficiently determines whether the parenthesis in a given string are properly matched or not.

Happy Coding :)