快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))

更新時(shí)間：2021年07月13日 11:28:03 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào)),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 20. Valid Parentheses 驗(yàn)證括號(hào)

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

這道題讓我們驗(yàn)證輸入的字符串是否為括號(hào)字符串，包括大括號(hào)，中括號(hào)和小括號(hào)。這里需要用一個(gè)棧，開始遍歷輸入字符串，如果當(dāng)前字符為左半邊括號(hào)時(shí)，則將其壓入棧中，如果遇到右半邊括號(hào)時(shí)，若此時(shí)棧為空，則直接返回 false，如不為空，則取出棧頂元素，若為對(duì)應(yīng)的左半邊括號(hào)，則繼續(xù)循環(huán)，反之返回 false，代碼如下：

方法一：

class Solution {
public:
    bool isValid(string s) {
        stack<char> parentheses;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]);
            else {
                if (parentheses.empty()) return false;
                if (s[i] == ')' && parentheses.top() != '(') return false;
                if (s[i] == ']' && parentheses.top() != '[') return false;
                if (s[i] == '}' && parentheses.top() != '{') return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
};

方法二：

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(20.驗(yàn)證括號(hào))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)驗(yàn)證括號(hào)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: