1.题目 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.
2 解法 时间复杂度O(N)
public class Solution { public boolean isValid(String s) { ArrayList<Character> arr = new ArrayList<Character>(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); if (ch == '(' || ch == '{' || ch == '[') { arr.add(ch); }else if (ch == ')' && !arr.isEmpty() && arr.get(arr.size() - 1) == '(') { arr.remove(arr.size() - 1); }else if (ch == '}' && !arr.isEmpty() && arr.get(arr.size() - 1) == '{') { arr.remove(arr.size() - 1); }else if (ch == ']' && !arr.isEmpty() && arr.get(arr.size() - 1) == '[') { arr.remove(arr.size() - 1); }else { return false; } } return arr.isEmpty() ? true : false; } }