C++實現LeetCode(20.驗證括號)

Posted on by

[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:

  1. Open brackets must be closed by the same type of brackets.
  2. 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

這道題讓我們驗證輸入的字符串是否為括號字符串，包括大括號，中括號和小括號。這裡需要用一個棧，開始遍歷輸入字符串，如果當前字符為左半邊括號時，則將其壓入棧中，如果遇到右半邊括號時，若此時棧為空，則直接返回 false，如不為空，則取出棧頂元素，若為對應的左半邊括號，則繼續循環，反之返回 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();
    }
};

到此這篇關於C++實現LeetCode(20.驗證括號)的文章就介紹到這瞭,更多相關C++實現驗證括號內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：