I am trying to solve this leetcode problem: 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.
I think I am almost correct and have been working on this problem for a long time but couldn't get the correct output especially a case where input is "())".
class Solution {
public boolean isValid(String s) {
Stack<Character> c = new Stack<>();
int n = s.length();
boolean bool = false;
if (s.isEmpty() | s == null) { // Correct
return true;
}
for (int i=0 ; i<n ; i++) {
if (s.charAt(i) == '{') {
c.push('{');
} else if (s.charAt(i) == '[') {
c.push('[');
} else if (s.charAt(i) == '(') {
c.push('(');
} else if (s.charAt(i) == '}' & c.peek() == '{') {
c.pop();
} else if (s.charAt(i) == ']' & c.peek() == '[') {
c.pop();
} else if (s.charAt(i) == ')' & c.peek() == '(') {
c.pop();
} else {
break;
}
}
if (c.isEmpty()) {
return true;
} else {
return false;
}
}
}
I think you should check stack's size before process these conditions.
else if (s.charAt(i) == '}' & c.peek() == '{') {
c.pop();
} else if (s.charAt(i) == ']' & c.peek() == '[') {
c.pop();
} else if (s.charAt(i) == ')' & c.peek() == '(') {
c.pop();
}