1. 題目
1.1 英文題目
Given a string s 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.
1.2 中文題目
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s ，判斷字串是否有效，
有效字串需滿足：
左括號必須用相同型別的右括號閉合，左括號必須以正確的順序閉合，
1.3輸入輸出
| 輸入 | 輸出 |
|---|---|
| s = "()" | true |
| s = "()[]{}" | true |
| s = "(]" | false |
| s = "([)]" | false |
| s = "{[]}" | true |
1.4 約束條件
- 1 <= s.length <= 104
- s consists of parentheses only '()[]{}'.
2. 分析
2.1 堆疊方法
這道題觀察規律可知，遍歷字符時，只需要看上一位即可，也就是說用堆疊的方法即可，代碼如下：
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> hash_map =
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};//定義一個哈希表，通過哈希表查看括號是否對應上
string temp(1, s[0]);//模擬堆疊，該字串只允許字符后入先出
for (unsigned int i = 1; i < s.size(); i++)//遍歷整個字串
{
if (temp.empty() || hash_map[temp.back()] != s[i])//如果堆疊為空，或者當前字符與堆疊頂字符不對應，則將該字符壓入堆疊
temp.push_back(s[i]);
else
temp.pop_back();//如果當前字符與堆疊頂字符對應，則將堆疊頂字符彈出
}
return temp.empty();
}
};
2.2 改進演算法
我上面的方法相當于是自己構造堆疊，但是其實c++有現成的堆疊模板，大神程式如下：
#include <stack>
class Solution {
public:
bool isValid(string s) {
stack<char> paren;
for (char& c : s) {
switch (c) {
case '(':
case '{':
case '[': paren.push(c); break;
case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
default: ; // pass
}
}
return paren.empty() ;
}
};
參考：https://leetcode.com/problems/valid-parentheses/discuss/9252/2ms-C%2B%2B-sloution
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/289445.html
標籤：C++