Valid Parentheses
LeetCode笔记 阅读(509)
编号 : 20 难度 : <font color="green">Easy</font> # 题目 : >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 > # 解 : ```Cpp class Solution { public: bool isValid(string s) { /* 查找匹配的括号 */ map<char, char> match = { {')', '('}, {']', '['}, {'}', '{'}, }; /* 区分是左括号还是又括号 */ string left = "([{"; string right = ")]}"; /* 用栈保存尚未闭合的左括号 */ stack<char> openBrackets; for(auto& ch : s) { /* 左括号入栈 */ if(left.find_first_of(ch) != string::npos) { openBrackets.push(ch); } else if(right.find_first_of(ch) != string::npos) { /* 没有左括号时读到右括号 */ if(openBrackets.empty()) { return false; } char leftBracket = openBrackets.top(); if(leftBracket == match[ch]) { /* 右括号匹配最后一个未闭合的左括号,左括号出栈 */ openBrackets.pop(); } else { /* 不匹配 */ return false; } } } /* 没有剩下未闭合的左括号 */ return openBrackets.empty(); } }; ``` # 分析 : 这道题要求检查一组完全由括号组成的字符串,是否符合逻辑。 用一个栈缓存未闭合的左括号,读到左括号就入栈,读到右括号就判断是否和栈顶的左括号匹配,如果匹配就出栈,不匹配就返回`false`。 读完整个字符串后,如果栈是空的,说明括号字符串符合逻辑,否则不符合逻辑。