题目:
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}" 输出: true
示例 3:
输入: "(]" 输出: false
示例 4:
输入: "([)]" 输出: false
示例 5:
输入: "{[]}" 输出: true
解答:
bool isValid(string s) { if (s.size() == 0) return false; if (s.size() % 2 == 1)//奇数个也不行 return false; unordered_map<char, char> map = { { '{', '}' }, { '[', ']' }, { '(', ')' } }; stack<char> stackLeft; for (char c : s) { if (c == '{' || c == '[' || c == '(')//如果是左括号,则入栈 { stackLeft.push(c); } else if (c == '}' || c == ']' || c == ')')//如果是右括号,则出栈一个,判断是否匹配,不匹配则返回false { if (stackLeft.empty()) //!!!判断是否为空,不然下面的top会出现问题 return false; char cCmp = stackLeft.top(); if (map[cCmp] == c) { stackLeft.pop(); continue; } else return false; } } if (stackLeft.empty()) //判断栈中是否为空,不为空则为false; return true; return false; }