Solution 1 - Stack with Mapped Closing Brackets

For each character in the string, if it's an opening bracket, push the corresponding closing bracket onto the stack. If it's a closing bracket, check if the stack is non-empty and the top matches the current character. If not, return False. At the end, the string is valid only if the stack is empty.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0020.1 - Valid Parentheses - Solution 1 - Stack with Mapped Closing Brackets """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isValid(self, s: str) -> bool:
        """Valid Parentheses Function"""
        stack = []

        for c in s:
            if c == "(":
                stack.append(")")
            elif c == "{":
                stack.append("}")
            elif c == "[":
                stack.append("]")
            elif not stack or stack.pop() != c:
                return False

        return not stack


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isValid("()"))         # True
    print(Solution().isValid("()[]{}"))     # True
    print(Solution().isValid("(]"))         # False
    print(Solution().isValid("([])"))       # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0020.1 - Valid Parentheses - Solution 1 - Stack with Mapped Closing Brackets */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Valid Parentheses Function */
    isValid(s) {
        const stack = [];
        const openingToClosing = { "(": ")", "{": "}", "[": "]" };

        for (const ch of s) {
            if (openingToClosing[ch]) {
                stack.push(openingToClosing[ch]);
            } else {
                if (stack.length === 0 || stack.pop() !== ch) {
                    return false;
                }
            }
        }
        return stack.length === 0;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.isValid("()"));      // true
    console.log(solution.isValid("()[]{}"));  // true
    console.log(solution.isValid("(]"));      // false
    console.log(solution.isValid("([])"));    // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0020.1 - Valid Parentheses - Solution 1 - Stack with Mapped Closing Brackets */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Valid Parentheses Function */
    isValid(s: string): boolean {
        const stack: string[] = [];
        const openingToClosing: Record<string, string> = {
            "(": ")",
            "{": "}",
            "[": "]",
        };

        for (const ch of s) {
            if (openingToClosing[ch]) {
                stack.push(openingToClosing[ch]);
            } else {
                if (stack.length === 0 || stack.pop() !== ch) {
                    return false;
                }
            }
        }
        return stack.length === 0;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.isValid("()"));      // true
    console.log(solution.isValid("()[]{}"));  // true
    console.log(solution.isValid("(]"));      // false
    console.log(solution.isValid("([])"));    // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0020.1 - Valid Parentheses - Solution 1 - Stack with Mapped Closing Brackets

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func isValid(s string) bool {
	stack := []rune{}
	openingToClosing := map[rune]rune{'(': ')', '{': '}', '[': ']'}

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

func testcase() {
	// Test Function
	fmt.Println(isValid("()"))     // true
	fmt.Println(isValid("()[]{}")) // true
	fmt.Println(isValid("(]"))     // false
	fmt.Println(isValid("([])"))   // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0020.1 - Valid Parentheses - Solution 1 - Stack with Mapped Closing Brackets

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Valid Parentheses Function
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();

        for ch in s.chars() {
            match ch {
                '(' => stack.push(')'),
                '{' => stack.push('}'),
                '[' => stack.push(']'),
                _ => {
                    if stack.pop() != Some(ch) {
                        return false;
                    }
                }
            }
        }
        stack.is_empty()
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
fn testcase() {
    // Test Function
    println!("{}", Solution::is_valid("()".to_string())); // true
    println!("{}", Solution::is_valid("()[]{}".to_string())); // true
    println!("{}", Solution::is_valid("(]".to_string())); // false
    println!("{}", Solution::is_valid("([])".to_string())); // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
fn main() {
    testcase();
}

Solution 2 - Stack with Dictionary Lookup

Use a dictionary to map each closing bracket to its corresponding opening bracket. For each character, if it's a closing bracket, pop the top of the stack and check if it matches the expected opening bracket. If it's an opening bracket, push it onto the stack.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0020.2 - Valid Parentheses - Solution 2 - Stack with Dictionary Lookup """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def isValid(self, s: str) -> bool:
        """Valid Parentheses Function"""
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for c in s:
            if c in mapping:
                top = stack.pop() if stack else "#"
                if mapping[c] != top:
                    return False
            else:
                stack.append(c)

        return not stack


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().isValid("()"))         # True
    print(Solution().isValid("()[]{}"))     # True
    print(Solution().isValid("(]"))         # False
    print(Solution().isValid("([])"))       # True


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

/** 0020.2 - Valid Parentheses - Solution 2 - Stack with Dictionary Lookup */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Valid Parentheses Function */
    isValid(s) {
        const stack = [];
        const closingToOpening = { ")": "(", "]": "[", "}": "{" };

        for (const ch of s) {
            if (closingToOpening[ch]) {
                const top = stack.length ? stack.pop() : "#";
                if (closingToOpening[ch] !== top) {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }
        return stack.length === 0;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.isValid("()"));      // true
    console.log(solution.isValid("()[]{}"));  // true
    console.log(solution.isValid("(]"));      // false
    console.log(solution.isValid("([])"));    // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0020.2 - Valid Parentheses - Solution 2 - Stack with Dictionary Lookup */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Valid Parentheses Function */
    isValid(s: string): boolean {
        const stack: string[] = [];
        const closingToOpening: Record<string, string> = {
            ")": "(",
            "]": "[",
            "}": "{",
        };

        for (const ch of s) {
            if (closingToOpening[ch]) {
                const top: string = stack.length ? (stack.pop() as string) : "#";
                if (closingToOpening[ch] !== top) {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }
        return stack.length === 0;
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.isValid("()"));      // true
    console.log(solution.isValid("()[]{}"));  // true
    console.log(solution.isValid("(]"));      // false
    console.log(solution.isValid("([])"));    // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0020.2 - Valid Parentheses - Solution 2 - Stack with Dictionary Lookup

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func isValid(s string) bool {
	stack := []rune{}
	closingToOpening := map[rune]rune{')': '(', ']': '[', '}': '{'}

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

func testcase() {
	// Test Function
	fmt.Println(isValid("()"))     // true
	fmt.Println(isValid("()[]{}")) // true
	fmt.Println(isValid("(]"))     // false
	fmt.Println(isValid("([])"))   // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
	testcase()
}

// 0020.2 - Valid Parentheses - Solution 2 - Stack with Dictionary Lookup

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Valid Parentheses Function
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();

        for ch in s.chars() {
            match ch {
                ')' | ']' | '}' => {
                    let expected = match ch {
                        ')' => '(',
                        ']' => '[',
                        _ => '{',
                    };
                    if stack.pop() != Some(expected) {
                        return false;
                    }
                }
                _ => stack.push(ch),
            }
        }
        stack.is_empty()
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
fn testcase() {
    // Test Function
    println!("{}", Solution::is_valid("()".to_string())); // true
    println!("{}", Solution::is_valid("()[]{}".to_string())); // true
    println!("{}", Solution::is_valid("(]".to_string())); // false
    println!("{}", Solution::is_valid("([])".to_string())); // true
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
fn main() {
    testcase();
}

0020 - Valid Parentheses

Solution 1 - Stack with Mapped Closing Brackets

Solution 2 - Stack with Dictionary Lookup