1
/**
2
 * @param {string} s
3
 * @return {boolean}
4
 */
5
var checkValidString = function (s) {
6
  let map = {};
7
  return check(s, 0, 0, map);
8
};
9

10
function check(s, index, open, map) {
11
  if (index == s.length) {
12
    return open == 0;
13
  }
14

15
  if (open < 0) {
16
    return false;
17
  }
18
  let string = index.toString() + "##" + open.toString();
19
  if (string in map) {
20
    return map[string];
21
  }
22

23
  if (s[index] == "(") {
24
    let l = check(s, index + 1, open + 1, map);
25
    map[string] = l;
26
    return l;
27
  } else if (s[index] == ")") {
28
    let r = check(s, index + 1, open - 1, map);
29
    map[string] = r;
30
    return r;
31
  } else {
32
    let lr =
33
      check(s, index + 1, open + 1, map) ||
34
      check(s, index + 1, open - 1, map) ||
35
      check(s, index + 1, open, map);
36
    map[string] = lr;
37
    return lr;
38
  }
39
}