Leetcode每日一題(20200814)

今日題目

T20 有效的括號(簡單，棧)

題目描述

給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串，判斷字串是否有效。

有效字串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字串可被認爲是有效字串。

範例 1:
輸入: 「()」
輸出: true

範例 2:
輸入: 「()[]{}」
輸出: true

標籤

棧

解析

直接利用棧進行匹配即可。

python解法

class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return True
        size = -1
        stack = list()
        for i in s:
            if i in ['(', '[', '{']:
                size += 1
                stack.append(i)
            else:
                if size < 0:
                    return False
                if i == ')':
                    if stack[size] == '(':
                        stack.pop()
                        size -= 1
                    else:
                        return False
                if i == ']':
                    if stack[size] == '[':
                        stack.pop()
                        size -= 1
                    else:
                        return False
                if i == '}':
                    if stack[size] == '{':
                        stack.pop()
                        size -= 1
                    else:
                        return False
        return len(stack) == 0

C++解法

class Solution
{
public:
    bool isValid(string s)
    {
        int len = s.size();
        stack<char> s1;
        for (char c : s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                s1.push(c);
            }
            else
            {
                if (s1.empty())
                {
                    return false;
                }
                char c1;
                switch (c)
                {
                case ')':
                    c1 = '[';
                    break;
                case ']':
                    c1 = '[';
                    break;
                case '}':
                    c1 = '{';
                    break;
                default:
                    c1 = '\0';
                    break;
                }
                if (c1 != s1.top())
                {
                    return false;
                }
                s1.pop();
            }
        }
        return s1.empty();
    }
};