博文中会简要介绍Leetcode P0020题目分析及解题思路。
“Valid Parentheses”是一道很经典的栈问题，它的衍生题有逆波兰表达式等，这道题的考察重点是栈的特点，即先进后出，根据这个特性，对括号进行配对并消除。
Given a string 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. Note that an empty string is also considered valid.
这道题的思路相对比较简单。核心是遇到左括号进栈，遇到右括号，若栈顶是匹配的括号则配对并消除，若非匹配括号，则直接返回false，认定括号串不合法。
以下是Java的题解代码实现。
class Solution {
public boolean isValid(String s) {
if (s == null || s.length() == 0)
return true;
if (s.length() == 1)
return false;
Deque<Character> stack = new LinkedList<>();
char[] chars = s.toCharArray();
for (int itr=0; itr<chars.length; ++itr) {
switch (chars[itr]) {
case '(': {
stack.addFirst(chars[itr]);
break;
}
case ')': {
if (stack.isEmpty() || stack.peekFirst() != '(')
return false;
stack.removeFirst();
break;
}
case '[': {
stack.addFirst(chars[itr]);
break;
}
case ']': {
if (stack.isEmpty() || stack.peekFirst() != '[')
return false;
stack.removeFirst();
break;
}
case '{': {
stack.addFirst(chars[itr]);
break;
}
case '}': {
if (stack.isEmpty() || stack.peekFirst() != '{')
return false;
stack.removeFirst();
break;
}
default:
return false;
}
}
return stack.isEmpty();
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool isValid(string s) {
if (s.length() == 0)
return true;
if (s.length() == 1)
return false;
stack<char> validation;
for (int itr=0; itr<s.length(); ++itr) {
switch (s[itr]) {
case '(':
validation.push(s[itr]);
break;
case ')':
if (validation.empty() || validation.top() != '(')
return false;
validation.pop();
break;
case '[':
validation.push(s[itr]);
break;
case ']':
if (validation.empty() || validation.top() != '[')
return false;
validation.pop();
break;
case '{':
validation.push(s[itr]);
break;
case '}':
if (validation.empty() || validation.top() != '{')
return false;
validation.pop();
break;
default:
return false;
}
}
return validation.empty();
}
};