20. Valid Parentheses [LeetCode]

20. Valid Parentheses

对比LeetCode125:Valid Palindrome

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

An input string is valid if:

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

Note that an empty string is also considered valid.

平衡符号判定问题，经典的栈应用问题(关于栈的应用还有几个经典场景：Postfix Expressions和Infix to Postfix Conversion ).

/**************************************************************************
 * 
 * 20. [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)
 * 
 * Given a string s 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.
 * 
 * Example 1:
 * Input: s = "()"
 * Output: true
 * 
 * Example 2:
 * Input: s = "()[]{}"
 * Output: true
 * 
 * Example 3:
 * Input: s = "(]"
 * Output: false
 * 
 * Similar Questions: 125. [Valid Palindrome]
 **************************************************************************/


int findPair(int s) {
    switch (s) {
        case ')': return '(';
        case ']': return '[';
        case '}': return '{';
        default : return -1;
    }
}

// 用数组模拟栈  index = -1 表示栈空  index指向栈顶元素
bool isValid(char * s){
    int len = strlen(s);
    if (len < 2) return false;
    
    int index = -1;
    char *ret = (char *)calloc(len, sizeof(char));
    
    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            index++;
            ret[index] = s[i];
        } else {
            if (index == -1) return false;
            if (ret[index] != findPair(s[i])) return false;
            index--;
        }
    }
    free(ret);
    return index == -1;
}