1
class Solution {
2
  public boolean checkValidString(String s) {
3
    Stack<Integer> stack = new Stack<>();
4
    Stack<Integer> star = new Stack<>();
5
    for (int i = 0; i < s.length(); i++) {
6
      if (s.charAt(i) == '(') stack.push(i);
7
      else if (s.charAt(i) == '*') star.push(i);
8
      else {
9
        if (!stack.isEmpty()) stack.pop();
10
        else if (!star.isEmpty()) star.pop();
11
        else return false;
12
      }
13
    }
14
    while (!stack.isEmpty()) {
15
      if (star.isEmpty()) return false;
16
      else if (stack.peek() < star.peek()) {
17
        star.pop();
18
        stack.pop();
19
      } else return false;
20
    }
21
    return true;
22
  }
23
}