[题目] 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.
[中文翻译] 给定一个只包含字符‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘和‘]’的字符串，确定输入字符串是否有效。 有效的字符串，括号以正确的顺序关闭，“()”和“()[]{}”都有效，但“(]”和“([)]”不是。
[解题思路] 本题为括号匹配问题。 使用堆栈，遍历字符串，当前字符为’(‘,’[‘或’{‘时，压栈，是’)’,’]’或’}’时，查看栈顶元素是否与当前字符匹配，如果匹配则弹出栈顶元素，否则字符串不合法。 等遍历完整个字符串，看一下栈是否为空，如果不为空，意味着有括号没有匹配，字符串不合法，否则，所有括号都按顺序匹配，字符串合法。
[C++代码]
class Solution {public: bool isValid(string s) { char* chs = new char[s.size()]; int index = 0; for (int i = 0; i < s.size(); i++) { char ch = s.at(i); if ('(' == ch || '[' == ch || '{' == ch) { chs[index++] = ch; } else { if (0 == index) return false; if (')' == ch && chs[index - 1] != '(') return false; if (']' == ch && chs[index - 1] != '[') return false; if ('}' == ch && chs[index - 1] != '{') return false; index--; } } delete chs; return 0 == index; }};新闻热点
疑难解答
