【LeetCode】20. 有效的括号(Valid Parent

点击 这里 跳转到LeetCode官网查看题目
点击 这里 跳转到LeetCode中国官网查看题目

20. Valid Parentheses

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

中文：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

思路：

• 保证左括号数量 和 右括号数量是相等的。
• 内层的括号先进行关闭（对应）
• 可以通过指针位置来实现判断数量关系
• 可以看看 2013的一道考研题 ，这题在思路上相当于那题的升级版，可以用同样的思想解决

Accept by C：

bool isValid(char * s){
    //获取字符串的长度
    int len = strlen(s); 
    //创建一个工作指针指向字符串起始位置
    char* s1 = s;
    //遍历字符串
    for(int i = 0 ; i < len ; ++i){
        switch(*(s+i)){
            //当检测到左括号，通过s1指针将其修改为对应右括号
            case '(':
                *s1++ = ')';
                break;
            case '{':
                *s1++ = '}';
                break;
            case '[':
                *s1++ = ']';
                break;
            default:
                //当第一次检测到右括号，此时需要满足:
                //         1.右括号不是第一个出现的
                //         2.右括号左侧与之对应的左括号与之匹配，
                //           这里我们修改过左括号，所以只需要判断它们是否相等
                if(s1 == s || *--s1 != *(s+i))
                    return false;
        }
    }
    //满足以上2个条件，并且左括号和右括号数量匹配，返回True
    return s1 == s;
    
}