Typical Code Interview Problem 1: Matching Parentheses

uwspstar March 1, 2023

Question:

Given a string s containing only the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the string is valid.

A string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Each closing bracket has a corresponding opening bracket of the same type.

Solution By ChatGPT

def is_valid(s: str) -> bool:
    stack = []  # create an empty stack to store opening brackets
    mapping = {")": "(", "}": "{", "]": "["}  # create a mapping of closing brackets to opening brackets
    for char in s:  # iterate over each character in the input string
        if char in mapping:  # if the character is a closing bracket
            top_element = stack.pop() if stack else "#"  # get the last opening bracket from the stack, or "#" if the stack is empty
            if mapping[char] != top_element:  # if the opening bracket does not match the corresponding closing bracket
                return False  # the string is not valid, return False
        else:  # if the character is an opening bracket
            stack.append(char)  # add it to the stack
    return not stack  # return True if the stack is empty (all opening brackets have been matched with closing brackets), False otherwise

2 thoughts on “Typical Code Interview Problem 1: Matching Parentheses”

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

这是一道经典的括号匹配问题，可以使用栈来解决。

具体地，遍历字符串 s 中的每个字符：

如果当前字符是左括号，则将其压入栈中。
如果当前字符是右括号，则需要判断栈顶元素是否为相应的左括号，如果不是则说明该字符串无效，直接返回 False。如果是相应的左括号，则将栈顶元素弹出。
遍历完字符串 s 后，如果栈为空，则说明该字符串是有效的，否则无效。
下面是 Python 代码实现：

def isValid(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 # 不匹配则返回 False else: stack.append(char) # 如果是左括号，则将其压入栈中 return not stack # 遍历完字符串 s 后，如果栈为空，则说明该字符串是有效的，否则无效。

其中，mapping 表示右括号与其对应的左括号的映射关系。注意，这里需要将空栈的情况也考虑到，避免出现 pop() 空栈的情况。

Comments are closed.