1. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: false

Problem Breakdown:

1. We create a dictionary that maps each closing bracket to its corresponding opening bracket. This allows us to quickly look up what opening bracket should match a closing bracket.

• closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }

2. We create a stack (using a list) to keep track of opening brackets as we encounter them. The stack is LIFO (Last In, First Out), which is perfect because the most recent opening bracket should be matched first.

• stack = []

3. We loop through each character in the string. For each character, we check if it is a closing bracket (i.e., if it exists in our dictionary).

• for c in s:
      if c in closeToOpen:

4. If it is a closing bracket, we check two conditions: (a) the stack is not empty, and (b) the top of the stack matches the corresponding opening bracket. If both conditions are true, we pop from the stack. Otherwise, the string is invalid.

• if stack and stack[-1] == closeToOpen[c]:
      stack.pop()
  else:
      return False

5. If the character is an opening bracket, we simply push it onto the stack.

• else:
      stack.append(c)

6. After processing all characters, the stack should be empty if all brackets were properly matched. If the stack is not empty, there are unmatched opening brackets.

• return True if not stack else False

Summary:

Use a stack to track opening brackets. When we encounter a closing bracket, we check if it matches the most recent opening bracket on the stack. If at any point there is a mismatch or the stack is empty when we need a match, the string is invalid. At the end, the stack must be empty for the string to be valid.

Time and Space Complexity:

Time Complexity: O(n) - we iterate through the string once, where n is the length of the string.

Space Complexity: O(n) - in the worst case, we push all characters onto the stack (e.g., all opening brackets).

Python Solution:

def isValid(s):
    closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }
    stack = []

    for c in s:
        if c in closeToOpen:
            if stack and stack[-1] == closeToOpen[c]:
                stack.pop()
            else:
                return False
        else:
            stack.append(c)

    return True if not stack else False

JavaScript Solution:

var isValid = function(s) {
    const closeToOpen = { ")" : "(", "]" : "[", "}" : "{" };
    const stack = [];

    for (let c of s) {
        if (c in closeToOpen) {
            if (stack.length > 0 && stack[stack.length - 1] === closeToOpen[c]) {
                stack.pop();
            } else {
                return false;
            }
        } else {
            stack.push(c);
        }
    }

    return stack.length === 0;
};

Java Solution:

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> closeToOpen = new HashMap<>();
        closeToOpen.put(')', '(');
        closeToOpen.put(']', '[');
        closeToOpen.put('}', '{');

        for (char c : s.toCharArray()) {
            if (closeToOpen.containsKey(c)) {
                if (!stack.isEmpty() && stack.peek() == closeToOpen.get(c)) {
                    stack.pop();
                } else {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }

        return stack.isEmpty();
    }
}