20.Valid Parentheses

发表于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 360 | 阅读时间 ≈ 1

题目描述

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

我的解法

解题思路

用一个string来做堆来储存左边的括号，如果遇到右边的括号就判断堆顶的左边括号和右边括号匹不匹配。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0)
            return false;
        string tmp;
        for (int i = 0; i < s.size(); i++){
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
                tmp.push_back(s[i]);
            else{
                if ((s[i] == ')' && *(tmp.end() - 1) == '(') || (s[i] == '}' && *(tmp.end() - 1) == '{') || (s[i] == ']' && *(tmp.end() - 1) == '['))
                    tmp.pop_back();
                else
                    return false;
            }
        }
        if (tmp.size() != 0)
            return false;
        return true;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Valid Parentheses.
Memory Usage: 8.3 MB, less than 97.67% of C++ online submissions for Valid
虽然可以完成任务可以代码长了点

高票解法

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char & c : s){
            switch(c) {
                case '(':
                case '[':
                case '{': paren.push(c); break;
                case ')': if(paren.empty() || paren.top() != '(') return false; else paren.pop(); break;
                case ']': if(paren.empty() || paren.top() != '[') return false; else paren.pop(); break;
                case '}': if(paren.empty() || paren.top() != '{') return false; else paren.pop(); break;
                default: ;
            }
        }
        return paren.empty();
    }
};

代码分析

用switch case和stack就能整洁很多