> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/20.-valid-parentheses.md).

# 20. Valid Parentheses

## 1.問題

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNoh9faEQl7D06ONTkN%2F-LNpAXbXgLctduuWowN5%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-10-02%20%E4%B8%8B%E5%8D%8810.27.53.png?alt=media\&token=2511665a-3287-43c4-bb44-652f02012351)

## 2.想法

* 提問
* function header, parameter
* test input
* 說明想法
  * 左括號時: 放到stack中
  * 右括號時: 
    * 若stack是空的或是左右無法match, 回傳false
    * pop stack
  * 最後回傳判斷stack是否為空
* 測試計算複雜度: O(n) , n是長的字串的長度

## **3.程式碼**

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