Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:


	Any left parenthesis '(' must have a corresponding right parenthesis ')'.
	Any right parenthesis ')' must have a corresponding left parenthesis '('.
	Left parenthesis '(' must go before the corresponding right parenthesis ')'.
	'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".


&nbsp;
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "(*)"
Output: true
Example 3:
Input: s = "(*))"
Output: true

&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 100
	s[i] is '(', ')' or '*'.


class Solution:
    def checkValidString(self, s: str) -> bool:
        left,right,star = deque(), deque(), deque() #indexes of all unmatched left right parens and all '*'
        # O(n) where n=len(s)
        for i,c in enumerate(s):
            if c == '(': # we just append left paren's index
                left.append(i)
            elif c == ')': # we check if we can find a match of left paren
                if left and left[-1] < i:
                    left.pop()
                else:
                    right.append(i)
            else: #'*' case we just add the postion
                star.append(i)
        if not left and not right: return True
        elif not star: return False #no star to save the string, return False
        l,r = 0 ,len(star)-1
        #O(n) since star will be length less than n
        # Note: left, right,and star are always kept in ascending order! And for any i in left, j in right, i > j, or they would have been matched in the previous for loop.
        while l<=r:
            if left:
                if left[-1]< star[r]: # we keep using right most star to match with right most '('
                    left.pop()
                    r -= 1
                else: return False # even the right most '*' can not match a '(', we can not fix the string.
            if right:
                if right[0] > star[l]:
                    right.popleft()
                    l += 1
                else: return False
            if not left and not right: return True #if after some fix, all matched, we return True
class Solution{
	public boolean checkValidString(String s){
		Stack<Integer> stack = new Stack<>();
		Stack<Integer> star = new Stack<>();
		for(int i=0;i<s.length();i++){
			if(s.charAt(i)=='(' ) 
                stack.push(i);
            else if(s.charAt(i)=='*') 
                star.push(i);
			else {
                if(!stack.isEmpty())
                         stack.pop();
                
               else if(!star.isEmpty())
                          star.pop();
                 else 
                          return false;
                
			}
		}
        while(!stack.isEmpty()){
            if(star.isEmpty()) 
                return false;
            else if( stack.peek()<star.peek())                
            {
                star.pop();
                stack.pop();
            }
            else
                 return false;
        }
		return true;
	}
}
class Solution {
public:
    bool checkValidString(string s) {
        unordered_map<int, unordered_map<int, bool>> m;
        return dfs(s, 0, 0, m);
    }

    // b: balanced number
    bool dfs (string s, int index, int b, unordered_map<int, unordered_map<int, bool>>& m) {
        if (index == s.length()) {
            if (b == 0 ) return true;
            else return false;
        }

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

        if (s[index] == '(') {
            m[index][b] = dfs(s, index+1, b+1, m);
        } else if (s[index] == ')') {
            m[index][b] = (b!= 0 && dfs(s, index+1, b-1, m));
        }else {
            m[index][b] = dfs(s,index+1, b, m) || dfs(s, index+1, b+1, m) ||
                    (b != 0 && dfs(s, index+1, b-1, m));
        }

        return m[index][b];
    }
};
/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
    let map = {}
    return check(s,0,0,map);
};

function check(s,index,open,map){
    if(index == s.length){
        return open == 0;
    }

    if(open < 0){
        return false;
    }
    let string = index.toString() + "##" + open.toString();
    if(string in map){
        return map[string]
    }

    if(s[index] == '('){
        let l = check(s,index+1,open+1,map)
        map[string] = l
        return l
    }else if (s[index] == ')'){
        let r = check(s,index+1,open-1,map)
        map[string] = r;
        return r
    }else {
        let lr = check(s,index+1,open+1,map) || check(s,index+1,open-1,map)
              || check(s,index+1,open,map)
        map[string] = lr;
        return lr
    }
}
Valid Parenthesis String