Given a string containing just the characters '('
, ')'
, '{'
, '}'
, '['
and ']'
,
determine if the input string is valid.
The brackets must close in the correct order, "()"
and "()[]{}"
are
all valid but "(]"
and "([)]"
are
not.
思路:这道题可以用栈来做。比如"("、“["、"{"表示压栈的操作,另外三个字符表示出栈的操作。当来一个出栈的字符,将栈顶元素出栈,看其是否匹配,不匹配则false,匹配则继续,直到string到尾部并且栈为空。
class Solution { public: bool isPush(char a) { if (a == '(' || a == '[' || a == '{') { return true; } return false; } bool isValid(string s) { stack<char> S; int len = s.length(); if (len == 0) { return false; } int k = 0; while(k < len || !S.empty()) { if (isPush(s[k])) { S.push(s[k]); ++k; continue; } if (S.empty()) { return false; } char top = S.top(); S.pop(); if (top - s[k] > 2) { return false; } ++k; } if (S.empty()) { return true; } return false; } };