1. 题目描述

problem link

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

2. 解题

栈最典型的应用之一,括号匹配。

如果遇到了正括号:

  • 直接无脑压栈,栈容量++

如果遇到了反括号:

  • 如果当前栈容量 == 0,则当前反括号不可能匹配,返回false
  • 否则让栈顶元素与当前反括号进行匹配,匹配上了栈容量--,没匹配上返回false

最终如果栈里还有元素则出现了不匹配,返回false,否则返回true

3. 代码

typedef int bool;
#define true 1
#define false 0

bool isValid(char * s) {
    char stack[5000] = { 0 };
    int size = 0;
    char* ptr = s;

    while (*ptr) {
        if (*ptr == '(' || *ptr == '{' || *ptr == '[') {  // 左括号
            stack[size++] = *ptr++;
        }
        else {
            if (size == 0) {  // 只有反括号没有正括号
                return false;
            }
            if ((stack[size - 1] == '(' && *ptr == ')') ||
                (stack[size - 1] == '[' && *ptr == ']') ||
                (stack[size - 1] == '{' && *ptr == '}')) {  // 匹配上了
                size--;
                ptr++;
            }
            else {  // 没匹配上
                return false;
            }
        }
    }

    return size == 0 ? true : false;
}
Last modification:September 8th, 2019 at 08:20 pm