Question:
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:
1 2
|
Input: "()" Output: true
|
Example 2:
1 2
|
Input: "()[]{}" Output: true
|
Example 3:
1 2
|
Input: "(]" Output: false
|
Example 4:
1 2
|
Input: "([)]" Output: false
|
Example 5:
1 2
|
Input: "{[]}" Output: true
|
My Answer:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
class { public boolean isValid(String s) { if(s.length()==0) return true; if(s.length()==1 ||s.charAt(0)==')' || s.charAt(0)==']' ||s.charAt(0)=='}') return false; Stack<Character> stack = new Stack<Character>(); for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(c =='(' || c =='[' || c =='{'){ stack.push(c); } else if(c == ')' && !stack.empty()){ if(stack.pop() != '(') return false; } else if(c == ']' && !stack.empty()){ if(stack.pop() != '[') return false; } else if(c == '}' && !stack.empty()){ if(stack.pop() != '{') return false; } else return false; } return stack.empty(); } }
|
Running time: 8ms
Better Answer 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
public static boolean isValid(String s) { if (s.isEmpty()) return true; Stack<Character> st = new Stack<>(); for (char c : s.toCharArray()) { if (st.isEmpty()) st.push(c); else { char last = st.peek(); if (c == '(' || c == '{' || c == '[') st.push(c); else if (c == ')' && last == '(' || c == '}' && last == '{' || c == ']' && last == '[') st.pop(); else return false; } } return st.isEmpty(); }
|
Better Answer 2:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
public boolean isValid(String s) { Stack<Character> stack = new Stack<Character>(); for (char c : s.toCharArray()) { if (c == '(') stack.push(')'); else if (c == '{') stack.push('}'); else if (c == '[') stack.push(']'); else if (stack.isEmpty() || stack.pop() != c) return false; } return stack.isEmpty(); }
|
近期评论