LeetCode #20 Valid Parentheses

問題概要

入力値：s(string)
出力値：bool
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
問題のリンク

入力例

Input: s="()"
Output: true

解答例1

計算量：O(n)
Recursion
Python

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        pair = {
            "(": ")",
            "{": "}",
            "[": "]"
        }
        for char in s:
            if len(stack) == 0:
                stack.append(char)
            elif stack[-1] not in pair:
                return False
            elif pair[stack[-1]] == char:
                stack.pop()
            else:
                stack.append(char)
        return len(stack) == 0

Runtime: 15ms
Beats: 55.47%

C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (auto c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else if (
                st.empty() ||
                (c == ')' && st.top() != '(') ||
                (c == ']' && st.top() != '[') ||
                (c == '}' && st.top() != '{')
            ) {
                return false;
            } else {
                st.pop();
            }
        }
        return st.empty();
    }
};

Runtime: 0ms
Beats: 100.0%