SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Intuition

The problem requires determining if a given string of brackets is valid. A string is valid if every open bracket has a corresponding closed bracket of the same type, and the brackets are closed in the correct order. To achieve this, we can use a stack data structure to keep track of the open brackets, ensuring that they are closed in the correct order.

Approach

1. Stack Usage: Initialize an empty stack to keep track of open brackets.

2. Mapping Brackets: Use a dictionary to map each closing bracket to its corresponding opening bracket.

3. Iterate Through String: Loop through each character in the string s:

   • If the character is a closing bracket, check if it matches the top element of the stack (i.e., the most recent unmatched opening bracket). If it does, pop the stack. If it doesn't match or the stack is empty, the string is invalid.
   • If the character is an opening bracket, push it onto the stack.

4. Final Check: After processing all characters, the stack should be empty if the string is valid (all brackets matched). If the stack is not empty, the string is invalid.

Complexity

Time Complexity:

O(n), where n is the length of the string. Each character is processed once.

Space Complexity:

O(n), in the worst case, all opening brackets are pushed onto the stack.

Code

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> v;
        unordered_map<char, char> p = {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };
        for (char c : s) {
            if (p.find(c) != p.end()) {
                v.push(c);
            } else {
                if (!v.empty() && p[v.top()] == c) {
                    v.pop();
                } else {
                    return false;
                }
            }
        }
        return v.empty();
    }
};

Python

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}
        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        
        return not stack

Java

class Solution {
    public boolean isValid(String s) {
        Stack<Character> v = new Stack<>();
        HashMap<Character, Character> p = new HashMap<>();
        p.put('(', ')');
        p.put('{', '}');
        p.put('[', ']');
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (p.containsKey(c)) {
                v.push(c);
            } else {
                if (!v.isEmpty() && p.get(v.peek()) == c) {
                    v.pop();
                } else {
                    return false;
                }
            }
        }
        return v.isEmpty();
    }
}

JavaScript

var isValid = function (s) {
    const a = s.split('');
    let v = [];
    const p = {
        "(": ")",
        "{": "}",
        "[": "]"
    };
    for (let i = 0; i < a.length; i++) {
        if (a[i] in p) {
            v.push(a[i]);
        } else {
            if (a[i] === p[v[v.length - 1]]) {
                v.pop();
            } else {
                return false;
            };
        };
    };
    return !v[0];
};