How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution?
The code is working, but I want to improve it.
The challenge I am facing is handling negative indices (count < 0) and shifting them to the positive side.
Problem link: https://leetcode.com/problems/valid-parenthesis-string/description/
Given a string
s
containing only three types of characters:'('
,')'
and'*'
, returntrue
ifs
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""
.Example 1:
Input:
s = "()"
Output:true
Example 2:
Input:
s = "(*)"
Output:true
Example 3:
Input:
s = "(*))"
Output:true
Constraints:
1 <= s.length <= 100
s[i]
is'('
,')'
or'*'
.
public static boolean checkValidStringMem(String s)
{
int n = s.length();
Boolean[][] mem = new Boolean[n][n + 1];
return checkValidStringMem(s, 0, 0, mem);
}
public static boolean checkValidStringMem(String s, int i, int count, Boolean[][] mem)
{
if (count < 0)
return false;
if (i == s.length())
return count == 0;
if (mem[i][count] != null)
return mem[i][count];
if (s.charAt(i) == '(')
return mem[i][count] = checkValidStringMem(s, i + 1, count + 1, mem);
else if (s.charAt(i) == ')')
return mem[i][count] = checkValidStringMem(s, i + 1, count - 1, mem);
else // '*' can be ')' or '(' or empty character
{
return mem[i][count] = checkValidStringMem(s, i + 1, count + 1, mem) ||
checkValidStringMem(s, i + 1, count - 1, mem) ||
checkValidStringMem(s, i + 1, count, mem);
}
}