1
class Solution {
2
 public:
3
  bool checkValidString(string s) {
4
    unordered_map<int, unordered_map<int, bool>> m;
5
    return dfs(s, 0, 0, m);
6
  }
7

8
  // b: balanced number
9
  bool dfs(string s, int index, int b, unordered_map<int, unordered_map<int, bool>> &m) {
10
    if (index == s.length()) {
11
      if (b == 0)
12
        return true;
13
      else
14
        return false;
15
    }
16

17
    if (m.count(index) && m[index].count(b)) return m[index][b];
18

19
    if (s[index] == '(') {
20
      m[index][b] = dfs(s, index + 1, b + 1, m);
21
    } else if (s[index] == ')') {
22
      m[index][b] = (b != 0 && dfs(s, index + 1, b - 1, m));
23
    } else {
24
      m[index][b] = dfs(s, index + 1, b, m) || dfs(s, index + 1, b + 1, m) ||
25
                    (b != 0 && dfs(s, index + 1, b - 1, m));
26
    }
27

28
    return m[index][b];
29
  }
30
};