| 1 | class Solution { |
| 2 | |
| 3 | public boolean checkValidString(String s) { |
| 4 | int count = 0; |
| 5 | Stack<Integer> op = new Stack<>(); |
| 6 | Stack<Integer> st = new Stack<>(); |
| 7 | |
| 8 | for (int i = 0; i < s.length(); ++i) { |
| 9 | if (s.charAt(i) == '(') op.push(i); // index of opening |
| 10 | else if (s.charAt(i) == ')') { |
| 11 | if (op.size() > 0) op.pop(); // if we have brackets |
| 12 | else if (st.size() > 0) st.pop(); // if not brackets do we have stars |
| 13 | else return false; // a closing bracket without opening and star |
| 14 | } else st.push(i); // index of star |
| 15 | } |
| 16 | // if we left with some opening bracket that over stars con cover up |
| 17 | while (op.size() > 0 && st.size() > 0) { |
| 18 | if (op.peek() > st.peek()) return false; |
| 19 | op.pop(); |
| 20 | st.pop(); |
| 21 | } |
| 22 | |
| 23 | return op.size() == 0; |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | // Time complexity: O(n) |