8. Validate Properly Nested Brackets

Given a string, check if all brackets (’()’, ’{}’, ’[]’) are properly matched and nested. Return 1 if valid, otherwise return 0.

Example

Input

code_snippet = if (a[0] > b[1]) { doSomething(); }

Output

1

Explanation

All brackets are properly matched: '(' with ')', '[' with ']', and '{' with '}'. No mismatches or improper nesting.

Input Format

• The function takes a single parameter, code_snippet, which is a STRING.

Constraints

• 0 <= code_snippet.length <= 1000
• code_snippet consists of printable ASCII characters (character codes 32 to 126 inclusive)
• code_snippet may contain any combination of ’(’, ’)’, ’{’, ’}’, ’[’, ’]’, letters, digits, symbols, and whitespace
• code_snippet may be empty

Output Format

• The function returns a BOOLEAN value, 1 for True and 0 for False.

Sample Input 0

int x = 42; // no brackets here

Sample Output 0

1

Sample Input 1

() {} []

Sample Output 1

1

Resolution

核心思路： 栈（Stack）。

括号匹配是经典的栈应用场景。利用栈“后进先出”（LIFO）的特性，可以完美解决嵌套问题。 例如 { ( ) }：

1. 遇到 { 入栈。
2. 遇到 ( 入栈。栈底是 {，栈顶是 (。
3. 遇到 ) 时，必须匹配最近的那个左括号，也就是栈顶的 (。匹配成功则 ( 出栈。
4. 遇到 } 时，必须匹配最近的左括号，此时栈顶是 {。匹配成功则 { 出栈。
5. 遍历结束，栈为空，说明全部匹配。

算法步骤：

1. 初始化一个空栈 stack，定义左括号集合、右括号集合，以及右括号到左括号的映射表（如 } -> {）。
2. 遍历字符串：
   • 如果是左括号：入栈。
   • 如果是右括号：弹出栈顶元素。
     • 如果栈为空（说明没有对应的左括号），或者弹出的左括号与当前右括号不匹配 -> 无效，返回 0。
     • 如果匹配，继续遍历。
   • 如果是其他字符：忽略。
3. 遍历结束后，检查栈是否为空：
   • 如果为空：说明所有左括号都闭合了 -> 有效，返回 1。
   • 如果不为空：说明还有未闭合的左括号 -> 无效，返回 0。

复杂度：

• 时间复杂度：O(n)，只需遍历一次字符串。
• 空间复杂度：O(n)，最坏情况下（全是左括号）栈的大小为 n。

同类题： LeetCode 20. 有效的括号。这是非常经典的面试题。

我的解法

function areBracketsProperlyMatched(code_snippet: string): boolean {
    // Write your code here
    const startSnippet = ['(', '{', '[']
    const endSnippet = [')', '}', ']']
    const endMap: any = {
        ')': '(',
        ']': '[',
        '}': '{',
    }
    const snippetStack: string[] = []
    for (let i = 0; i < code_snippet.length; i++) {
        const curVar = code_snippet[i]
        if (startSnippet.includes(curVar)) {
            snippetStack.push(curVar)
        } else if (endSnippet.includes(curVar)) {
            const tmp = snippetStack.pop()
            if (!tmp || endMap[curVar] !== tmp) {
                return false
            }
        }
    }
    if (snippetStack?.length) {
        return false
    }
    return true
}