開源地址：https://github.com/jiauzhang/algorithms
題目
/*
* https://leetcode-cn.com/problems/valid-parentheses
* 給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串，判斷字串是否有效，
* 有效字串需滿足：
* 左括號必須用相同型別的右括號閉合，
* 左括號必須以正確的順序閉合，
*
* 注意空字串可被認為是有效字串，
*/
示例
/*
* 示例 1:
* 輸入: "()"
* 輸出: true
*
* 示例 2:
* 輸入: "()[]{}"
* 輸出: true
*
* 示例 3:
* 輸入: "(]"
* 輸出: false
*
* 示例 4:
* 輸入: "([)]"
* 輸出: false
*
* 示例 5:
* 輸入: "{[]}"
* 輸出: true
*/
解題思路
/*
* 1. 有效括號肯定都是成對出現的，如果一個字串是有效的
* 那么最外側的括號括起來的子字串一定也是有效的
* 即原問題可分解為子問題
* 2. 如果反過來想，那么最內層的一定也是有效的，而且是緊挨著的
* 例如 {[()]}, 如果把這個字串逐個壓入堆疊中，那么我們先
* 接收到的是開括號，后接收到的是閉括號，這就是為什么程式中
* open_close 的映射關系是反著寫的
* 3. 當接收到最內層時，緊接著就是最內層的閉括號，依次到最外層
* 當此時逐個消去時候，情況如下
* {[( --> {[() --> {[ --> {[] --> { --> {} --> empty
*/
示例代碼
class Solution {
public:
bool isValid(string s) {
if (s.size() == 0)
return true;
stack<char> stk;
unordered_map<char, char> open_close = {
{')', '('},
{'}', '{'},
{']', '['}
};
for (int i=0; i<s.size(); i++) {
if (stk.size() == 0) {
stk.push(s[i]);
} else if (stk.top() == open_close[s[i]]) {
stk.pop();
} else {
stk.push(s[i]);
}
}
return (stk.size() == 0);
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10531.html
標籤：其他
上一篇：求華為三層交換機配置，帶命令