Valid Parenthesis String

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

Solution : Time Complexity (O(3^n))

JAVA
1class Solution {
2    public boolean checkValidString(String s) {
3        // Start recursive helper with index 0 and count 0
4        return helper(0, 0, s);
5    }
6
7    public boolean helper(int idx, int count, String s) {
8        // If at any point count becomes negative, it means there are more ')' than '('
9        if (count < 0) return false;
10
11        // If we have processed the entire string, check if all open brackets are closed
12        if (idx == s.length()) {
13            return count == 0;
14        }
15
16        boolean ans = false;
17
18        // If the current character is '(', we increase the open count
19        if (s.charAt(idx) == '(') {
20            ans = helper(idx + 1, count + 1, s);
21        }
22        // If the current character is ')', we decrease the open count
23        else if (s.charAt(idx) == ')') {
24            ans = helper(idx + 1, count - 1, s);
25        }
26        // If the character is '*', it can be '(', ')' or an empty string
27        else {
28            // Try all 3 possibilities: count+1 for '(', count-1 for ')', count for empty
29            for (int i = -1; i <= 1; i++) {
30                ans = ans | helper(idx + 1, count + i, s);
31            }
32        }
33
34        return ans;
35    }
36}
37

Optimized Solution with memoization approach Time Complexity (O(n^2))

JAVA
1// Time Complexity: O(n^2) due to memoization of (idx, count) states
2// Space Complexity: O(n^2) for the memo map + O(n) recursion stack
3
4class Solution {
5    // Memoization map to store already computed (index#count) combinations
6    HashMap<String, Boolean> memo = new HashMap<>();
7
8    public boolean checkValidString(String s) {
9        // Start checking from index 0 and initial open parenthesis count = 0
10        return helper(0, 0, s);
11    }
12
13    public boolean helper(int idx, int count, String s) {
14        // Create a unique key for the current state
15        String k = idx + "#" + count;
16
17        // If open parentheses count goes negative, invalid state (more ')' than '(')
18        if (count < 0) {
19            memo.put(k, false);
20            return false;
21        }
22
23        // If we've reached the end of the string, valid only if all open '(' are matched
24        if (idx == s.length()) {
25            memo.put(k, count == 0);
26            return count == 0;
27        }
28
29        // Return previously stored result if this state was already computed
30        if (memo.containsKey(k)) return memo.get(k);
31
32        boolean ans = false;
33
34        // Case 1: Current char is '(' → increase open count
35        if (s.charAt(idx) == '(') {
36            ans = helper(idx + 1, count + 1, s);
37        }
38        // Case 2: Current char is ')' → decrease open count
39        else if (s.charAt(idx) == ')') {
40            ans = helper(idx + 1, count - 1, s);
41        }
42        // Case 3: Current char is '*' → try all 3 possibilities
43        else {
44            for (int i = -1; i < 2; i++) {
45                // i = -1 → treat '*' as ')'
46                // i =  0 → treat '*' as ''
47                // i =  1 → treat '*' as '('
48                ans = ans | helper(idx + 1, count + i, s);
49            }
50        }
51
52        // Memoize result before returning
53        memo.put(k, ans);
54        return ans;
55    }
56}