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.
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
一个仅由 '(', ')', '{', '}', '[' 和 ']' 组成的字符串，判断是否符合要求：
- 判断符号是否成对；
- 成对的符号要在对立的位置。
空字符串也是符合要求的。
解：
思路一，成对符号前面为a，后面为b。用一个map去记录成对的符号 b->a 的映射，用一个 stack 去记录 a，利用 stack 先进后出的特性去完成匹配。从头开始遍历，判断当前符号是否存在map中，存在，表明是b，那么取出map中对应的a去与stack中最后加入的符号进行匹配，匹配不上，完了，这肯定不是合法的，直接return false；能匹配上，stack.pop()。如果是a，加入到stack中。到最后，如果stack是空的，说明是合法的。由于只进行一轮遍历，时间复杂度为O(n)，空间复杂度，最坏的情况下，比如全为左符号，需要O(n)。
思路二，有一个特别巧的思路，写个死循环，一直把成对的符号替换成空，直到替换之后，长度没有变。最后字符串不为空，则表示不合法。
以下为代码：
public boolean isValid(String s) {
int length;
do {
length = s.length();
s = s.replace("()", "").replace("{}", "").replace("[]", "");
} while (length != s.length());
return s.isEmpty();
}
虽然思路二思路、代码都很简单，但是时间复杂复杂度很高，replace使用正则去匹配，然后再去替换，内部还有一层循环，最坏情况下需要循环n/2次，但是一次要匹配3次。时间复杂度约为O(n2)。
