20. Valid Parentheses

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: s = “()”

Output: true

Example 2:

Input: s = “()[]{}”

Output: true

Example 3:

Input: s = “(]”

Output: false

Example 4:

Input: s = “([])”

Output: true

Constraints:

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

Problem Description

The problem presents a scenario in which we are given a string s consisting of six possible characters: the opening and closing brackets of three types—parentheses (), square brackets [], and curly braces {}. The challenge is to determine whether this string represents a sequence of brackets that is considered valid based on certain rules. A string of brackets is deemed valid if it satisfies the following conditions:

1. Each opening bracket must be closed by a closing bracket of the same type.
2. Opening brackets must be closed in the correct order. That means no closing bracket should interrupt the corresponding pair of an opening bracket.
3. Each closing bracket must have an associated opening bracket of the same type before it.

For example, a string "(())" is valid because each opening parenthesis ( has a corresponding closing parenthesis ) that occurs later in the string, and they are properly nested and ordered.

Intuition

The intuition behind the solution utilizes a common data structure known as a stack, which operates on a last-in, first-out (LIFO) principle. This principle mimics the necessary behavior for tracking opening brackets and ensuring they are closed in the correct order. The steps followed in the solution are:

1. Initialize an empty stack to keep track of opening brackets.
2. Traverse the input string character by character.
3. When an opening bracket is encountered ('(', '[', or '{'), push it onto the stack. This represents waiting for a closing bracket to match.
4. When a closing bracket is encountered (')', ']', or '}'), check if it forms a pair with the last opening bracket added to the stack (i.e., on top of the stack).
5. If the stack is empty (no opening bracket available to match) or the closing bracket does not form a valid pair with the opening bracket on top of the stack, we know the string is invalid, and we immediately return False.
6. If we successfully traverse the entire input string and the stack is empty, meaning all opening brackets have been matched correctly, we return True. If the stack is not empty, it indicates there are unmatched opening brackets, and therefore, the string is invalid.

The concise implementation of this algorithm ensures that both the correct type and order of brackets are validated for the string to be considered valid.

Solution Approach

The solution utilizes a stack data structure to track opening brackets and ensure they have the appropriate closing brackets. Let’s walk through the implementation step by step:

1. Initialize a Stack: A list named stk is created to serve as a stack.
2. Pairs Set: We define a set d containing string representations of the valid bracket pairs: '()', '[]', and '{}'. This helps quickly check if an encountered closing bracket correctly pairs with the last opening bracket on the stack.
3. Iterate Over the String: The algorithm iterates over each character c in the input string s.
   • Opening Bracket: If c is an opening bracket ('(', '[', or '{'), it is pushed onto stk, waiting for the corresponding closing bracket.
   • Closing Bracket: If c is a closing bracket (')', ']', or '}'):
     • The stack is checked to ensure it’s not empty, which would mean there’s no opening bracket to match the closing one.
     • If the stack is not empty, the top element is popped. We concatenate it with c to check if they form a valid pair by checking against set d.
     • If either condition fails – the stack was empty or the concatenation of the popped element with c does not form a valid pair – the function immediately returns False because we’ve detected an invalid bracket sequence.
4. Final Stack Check: After processing all characters in the string, the algorithm checks if the stack is empty. An empty stack implies all opening brackets were properly matched and closed.
   • If the stack is empty (return not stk), it indicates a valid bracket sequence and returns True.
   • If the stack is not empty, some opening brackets were not closed, thus the function returns False, representing an invalid bracket sequence.

The solution is efficient with a linear time complexity, O(n), where n is the length of the string s. It only requires a single pass through the string and constant-time operations for each character. The space complexity is also O(n), in the worst case where the string consists entirely of opening brackets, which would all be pushed onto the stack.

Example Walkthrough

Let’s consider a small example to clearly understand the solution approach. Suppose we are given the string s = "{[()()]}". We want to determine if this string represents a valid sequence of brackets. Following the solution steps:

1. Initialize a Stack: We start with an empty list stk that will be used as our stack.
2. Pairs Set: We have a predefined set d that contains '()', '[]', and '{}' to represent valid bracket pairs.
3. Iterating Over the String: We iterate through each character in the string s.
   • For the first character {, it’s an opening bracket, so we push it onto stk.
   • For the second character [, it’s also an opening bracket, so we push it onto stk.
   • For the third character (, another opening bracket gets pushed onto stk.
   • The fourth character ) is a closing bracket, so we pop the last element (, which matches the closing bracket, forming a valid pair (). So far so good.
   • The fifth character ( is once again an opening bracket and is pushed onto stk.
   • The sixth character ) is a closing bracket, and popping from stk gives us the matching (, forming another valid pair. We continue this process for the remaining characters.
   • The seventh character ] is a closing bracket, and popping from stk gives us [, which is the correct complement, forming the pair [].
   • Finally, the last character } is a closing bracket, and after popping from stk we get {, its correct opening pair, forming {}.
4. Final Stack Check: At the end of iteration, stk is empty because every opening bracket has been matched with the correct closing bracket in the proper order.

Since the stack is empty, we return True, indicating that the given string s = "{[()()]}" is a valid sequence of brackets. Our solution has correctly determined the validity by using a stack to manage the ordering and pairing of the brackets.

Solution Implementation

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack;
        unordered_map<char, char> mapping = {{')', '('}, {']', '['}, {'}', '{'}};

        for (char c : s) {
            if (mapping.find(c) == mapping.end()) {
                stack.push(c);
            } else if (!stack.empty() && mapping[c] == stack.top()) {
                stack.pop();
            } else {
                return false;
            }
        }

        return stack.empty();        
    }
};
        

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

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

        return stack.isEmpty();        
    }
}
        

class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '[]'in s or '{}' in s:
            s = s.replace('()','').replace('[]','').replace('{}','')
        return False if len(s) !=0 else True
        

bool match(char a, char b) {
    return (a == '(' && b == ')') || (a == '{' && b == '}') ||
           (a == '[' && b == ']');
}

bool isValid(char* s) {
    int len = strlen(s);
    char stack[len];
    int top = -1;
    char popped_ch;

    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            stack[++top] = s[i];
        } else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
            if (top == -1)
                return false;
            popped_ch = stack[top--];
            if (!match(popped_ch, s[i]))
                return false;
        }
    }

    return (top == -1); 
}
        

public class Solution {
    public bool IsValid(string s) {
        while (s.Contains("()") || s.Contains("[]") || s.Contains("{}"))
        {
            s = s.Replace("()", "").Replace("[]", "").Replace("{}", "");
        }

        return s.Length == 0;
    }
}
        

var isValid = function(s) {   
    const stack = [];
    
    for (let i = 0 ; i < s.length ; i++) {
        let c = s.charAt(i);
        switch(c) {
            case '(': stack.push(')');
                break;
            case '[': stack.push(']');
                break;
            case '{': stack.push('}');
                break;
            default:
                if (c !== stack.pop()) {
                    return false;
                }
        }
    }
    
    return stack.length === 0;
};
        

function isValid(s: string): boolean {

    const stack : string[] = [];
    const bracketMap = {

         ')': '(',
        '}' : '{',
        ']' : '['
    }

    for(let char of s){
        if(char === '(' || char === '{' || char ==='[' ){
            stack.push(char)
        } else {

            if (stack.length === 0 || stack.pop() !== bracketMap[char]) {
                return false;
            }
        }
    
    };
    
    return stack.length ===0;
}
        

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function isValid($s) {
        $pairs = ['(' => ')', '{' => '}', '[' => ']'];
        $stack = [];
        $n = strlen($s);
        for ($i = 0; $i <; $n; $i++) {
            if (in_array($s[$i], ['(','{','['])) { 
                array_push($stack, $s[$i]);
            }
            else {
                $previous = array_pop($stack);
                if ($pairs[$previous] !== $s[$i]) { return false; }
            }
        }
        return (count($stack) === 0) ? true : false;
    }
}
        

class Solution {
    func isValid(_ s: String) -> Bool {
        
        guard s.count % 2 == 0 else { return false }
        
        var stack: [Character] = []
        
        for ch in s {
            switch ch {
            case "(": stack.append(")")
            case "[": stack.append("]")
            case "{": stack.append("}")
            default:
                if stack.isEmpty || stack.removeLast() != ch {
                    return false
                }
            }
        }
        
        return stack.isEmpty
    }
}
        

class Solution {
    fun isValid(s: String): Boolean {
        if (s == "") { return true }
        val simplified = s.replace("()", "").replace("{}", "").replace("[]", "")
        if (simplified == s) { return false }
        return isValid(simplified)
    }
}
        

class Solution {
 bool isValid(String s) {
  String d1 = "()";
  String d2 = "{}";
  String d3 = "[]";
  while (s.isNotEmpty) {
    if (s.contains(d1)) {
     s = s.replaceAll(d1, '');
    } else if (s.contains(d2)) {
     s = s.replaceAll(d2, '');
    } else if (s.contains(d3)) {
     s = s.replaceAll(d3, '');
    } else {
      return false;
    }
  }
  return true;
 }
}
        

func isValid(s string) bool {
if len(s) == 0 || len(s)%2 == 1 {
		return false
	}
    
	pairs := map[rune]rune{
		'(': ')',
		'{': '}',
		'[': ']',
	}
	stack := []rune{}

	for _, r := range s {
		if _, ok := pairs[r]; ok {
			stack = append(stack, r)
		} else if len(stack) == 0 || pairs[stack[len(stack)-1]] != r {
			return false
		} else {
			stack = stack[:len(stack)-1]
		}
	}

	return len(stack) == 0
}