Valid Parenthesis String
Valid Parenthesis String Problem
You are given a string s consisting of only three types of characters: ‘(‘ , ‘)’, and ‘*’. Return true if the string is valid; otherwise, return false.
A string is considered valid if it satisfies all the following conditions:
- Each ‘(‘ must have a matching ‘)’ and each ‘)’ must have a matching ‘(‘.
- ‘(‘ must always appear before its matching ‘)’.
- ‘*’ character can be treated as ‘(‘, ‘)’, or an empty string (” “).
Examples related Valid Parenthesis String
Example 1:
Input: s = "((**)"
Output: true
Explanation: One of the '*' could be a ')' and the other could be an empty string.
Output: true
Explanation: One of the '*' could be a ')' and the other could be an empty string.
Example 2:
Input: s = "(((*)"
Output: false
Explanation: String is not valid because there is an extra '(' at the beginning, regardless of the extra '*'.
Output: false
Explanation: String is not valid because there is an extra '(' at the beginning, regardless of the extra '*'.
Constraints:
1 <= s.length <= 100
Methods to Solve Valid Parenthesis String
There are mainly 6 approach to solve Reverse Nodes In K Group problem:
- Recursion Method
- Dynamic Programming Top Down
- Dynamic Programming Bottom Up
- Dynamic Programming Spaced Optimized
- Stack
- Greedy
1. Recursion Method
- This approach explores all possible interpretations of the * character (as (, ), or empty) by recursively validating each case. It is straightforward but can be slow due to redundant computations.
- Time complexity: O(3^n)
- Space complexity: O(n)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkValidString(string s) {
return dfs(0, 0, s);
}
private:
bool dfs(int i, int open, const string& s) {
if (open < 0) return false;
if (i == s.size()) return open == 0;
if (s[i] == '(') {
return dfs(i + 1, open + 1, s);
} else if (s[i] == ')') {
return dfs(i + 1, open - 1, s);
} else {
return dfs(i + 1, open, s) ||
dfs(i + 1, open + 1, s) ||
dfs(i + 1, open - 1, s);
}
}
};
Java
public class Solution {
public boolean checkValidString(String s) {
return dfs(0, 0, s);
}
private boolean dfs(int i, int open, String s) {
if (open < 0) return false;
if (i == s.length()) return open == 0;
if (s.charAt(i) == '(') {
return dfs(i + 1, open + 1, s);
} else if (s.charAt(i) == ')') {
return dfs(i + 1, open - 1, s);
} else {
return dfs(i + 1, open, s) ||
dfs(i + 1, open + 1, s) ||
dfs(i + 1, open - 1, s);
}
}
}
Python
class Solution:
def checkValidString(self, s: str) -> bool:
def dfs(i, open):
if open < 0:
return False
if i == len(s):
return open == 0
if s[i] == '(':
return dfs(i + 1, open + 1)
elif s[i] == ')':
return dfs(i + 1, open - 1)
else:
return (dfs(i + 1, open) or
dfs(i + 1, open + 1) or
dfs(i + 1, open - 1))
return dfs(0, 0)
JavaScript
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
checkValidString(s) {
function dfs(i, open) {
if (open < 0) return false;
if (i === s.length) return open === 0;
if (s[i] === '(') {
return dfs(i + 1, open + 1);
} else if (s[i] === ')') {
return dfs(i + 1, open - 1);
} else {
return dfs(i + 1, open) ||
dfs(i + 1, open + 1) ||
dfs(i + 1, open - 1);
}
}
return dfs(0, 0);
}
}
2. Dynamic Programming Top Down Method
- Use memorization to optimize recursion by storing already-computed results for specific states, avoiding repeated calculations.
- This reduces redundant work and speeds up the solution.
- Time complexity: O(n^2)
- Space complexity: O(n^2)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
memo = vector>(n + 1, vector(n + 1, -1));
return dfs(0, 0, s);
}
private:
vector> memo;
bool dfs(int i, int open, const string& s) {
if (open < 0) return false;
if (i == s.size()) return open == 0;
if (memo[i][open] != -1) return memo[i][open] == 1;
bool result;
if (s[i] == '(') {
result = dfs(i + 1, open + 1, s);
} else if (s[i] == ')') {
result = dfs(i + 1, open - 1, s);
} else {
result = (dfs(i + 1, open, s) ||
dfs(i + 1, open + 1, s) ||
dfs(i + 1, open - 1, s));
}
memo[i][open] = result ? 1 : 0;
return result;
}
};
Java
public class Solution {
public boolean checkValidString(String s) {
int n = s.length();
Boolean[][] memo = new Boolean[n + 1][n + 1];
return dfs(0, 0, s, memo);
}
private boolean dfs(int i, int open, String s, Boolean[][] memo) {
if (open < 0) return false;
if (i == s.length()) return open == 0;
if (memo[i][open] != null) return memo[i][open];
boolean result;
if (s.charAt(i) == '(') {
result = dfs(i + 1, open + 1, s, memo);
} else if (s.charAt(i) == ')') {
result = dfs(i + 1, open - 1, s, memo);
} else {
result = (dfs(i + 1, open, s, memo) ||
dfs(i + 1, open + 1, s, memo) ||
dfs(i + 1, open - 1, s, memo));
}
memo[i][open] = result;
return result;
}
}
Python
class Solution:
def checkValidString(self, s: str) -> bool:
n = len(s)
memo = [[None] * (n + 1) for _ in range(n + 1)]
def dfs(i, open):
if open < 0:
return False
if i == n:
return open == 0
if memo[i][open] is not None:
return memo[i][open]
if s[i] == '(':
result = dfs(i + 1, open + 1)
elif s[i] == ')':
result = dfs(i + 1, open - 1)
else:
result = (dfs(i + 1, open) or
dfs(i + 1, open + 1) or
dfs(i + 1, open - 1))
memo[i][open] = result
return result
return dfs(0, 0)
JavaScript
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
checkValidString(s) {
const n = s.length;
const memo = Array.from({ length: n + 1 }, () =>
Array(n + 1).fill(null));
function dfs(i, open) {
if (open < 0) return false;
if (i === n) return open === 0;
if (memo[i][open] !== null) return memo[i][open];
let result;
if (s[i] === '(') {
result = dfs(i + 1, open + 1);
} else if (s[i] === ')') {
result = dfs(i + 1, open - 1);
} else {
result = dfs(i + 1, open) ||
dfs(i + 1, open + 1) ||
dfs(i + 1, open - 1);
}
memo[i][open] = result;
return result;
}
return dfs(0, 0);
}
}
3. Dynamic Programming Bottom Up Method
- Build a table to solve the problem iteratively, starting from smaller subproblems and combining results. It systematically tracks valid states for substrings, ensuring efficient validation.
- Time complexity: O(n^2)
- Space complexity: O(n^2)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
vector> dp(n + 1, vector(n + 1, false));
dp[n][0] = true;
for (int i = n - 1; i >= 0; --i) {
for (int open = 0; open < n; ++open) {
bool res = false;
if (s[i] == '*') {
res |= dp[i + 1][open + 1];
if (open > 0) res |= dp[i + 1][open - 1];
res |= dp[i + 1][open];
} else {
if (s[i] == '(') {
res |= dp[i + 1][open + 1];
} else if (open > 0) {
res |= dp[i + 1][open - 1];
}
}
dp[i][open] = res;
}
}
return dp[0][0];
}
};
Java
public class Solution {
public boolean checkValidString(String s) {
int n = s.length();
boolean[][] dp = new boolean[n + 1][n + 1];
dp[n][0] = true;
for (int i = n - 1; i >= 0; i--) {
for (int open = 0; open < n; open++) {
boolean res = false;
if (s.charAt(i) == '*') {
res |= dp[i + 1][open + 1];
if (open > 0) res |= dp[i + 1][open - 1];
res |= dp[i + 1][open];
} else {
if (s.charAt(i) == '(') {
res |= dp[i + 1][open + 1];
} else if (open > 0) {
res |= dp[i + 1][open - 1];
}
}
dp[i][open] = res;
}
}
return dp[0][0];
}
}
Python
class Solution:
def checkValidString(self, s: str) -> bool:
n = len(s)
dp = [[False] * (n + 1) for _ in range(n + 1)]
dp[n][0] = True
for i in range(n - 1, -1, -1):
for open in range(n):
res = False
if s[i] == '*':
res |= dp[i + 1][open + 1]
if open > 0:
res |= dp[i + 1][open - 1]
res |= dp[i + 1][open]
else:
if s[i] == '(':
res |= dp[i + 1][open + 1]
elif open > 0:
res |= dp[i + 1][open - 1]
dp[i][open] = res
return dp[0][0]
JavaScript
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
checkValidString(s) {
const n = s.length;
const dp = Array.from({ length: n + 1 }, () =>
Array(n + 1).fill(false));
dp[n][0] = true;
for (let i = n - 1; i >= 0; i--) {
for (let open = 0; open < n; open++) {
let res = false;
if (s[i] === '*') {
res ||= dp[i + 1][open + 1];
if (open > 0) res ||= dp[i + 1][open - 1];
res ||= dp[i + 1][open];
} else {
if (s[i] === '(') {
res ||= dp[i + 1][open + 1];
} else if (open > 0) {
res ||= dp[i + 1][open - 1];
}
}
dp[i][open] = res;
}
}
return dp[0][0];
}
}
4. Dynamic Programming Space Optimized
Method
This approach improves the Bottom-Up method by reducing the memory usage to a single dimension, keeping track of only necessary information for validating the string.
- Time complexity: O(n^2)
- Space complexity: O(n)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkValidString(string s) {
int n = s.size();
vector dp(n + 1, false);
dp[0] = true;
for (int i = n - 1; i >= 0; --i) {
vector newDp(n + 1, false);
for (int open = 0; open < n; ++open) {
if (s[i] == '*') {
newDp[open] = dp[open + 1] ||
(open > 0 && dp[open - 1]) || dp[open];
} else if (s[i] == '(') {
newDp[open] = dp[open + 1];
} else if (open > 0) {
newDp[open] = dp[open - 1];
}
}
dp = newDp;
}
return dp[0];
}
};
Java
public class Solution {
public boolean checkValidString(String s) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = n - 1; i >= 0; i--) {
boolean[] newDp = new boolean[n + 1];
for (int open = 0; open < n; open++) {
if (s.charAt(i) == '*') {
newDp[open] = dp[open + 1] ||
(open > 0 && dp[open - 1]) || dp[open];
} else if (s.charAt(i) == '(') {
newDp[open] = dp[open + 1];
} else if (open > 0) {
newDp[open] = dp[open - 1];
}
}
dp = newDp;
}
return dp[0];
}
}
Python
class Solution:
def checkValidString(self, s: str) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n - 1, -1, -1):
new_dp = [False] * (n + 1)
for open in range(n):
if s[i] == '*':
new_dp[open] = (dp[open + 1] or
(open > 0 and dp[open - 1]) or
dp[open])
elif s[i] == '(':
new_dp[open] = dp[open + 1]
elif open > 0:
new_dp[open] = dp[open - 1]
dp = new_dp
return dp[0]
JavaScript
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
checkValidString(s) {
const n = s.length;
let dp = Array(n + 1).fill(false);
dp[0] = true;
for (let i = n - 1; i >= 0; i--) {
const newDp = Array(n + 1).fill(false);
for (let open = 0; open < n; open++) {
if (s[i] === '*') {
newDp[open] = dp[open + 1] ||
(open > 0 && dp[open - 1]) || dp[open];
} else if (s[i] === '(') {
newDp[open] = dp[open + 1];
} else if (open > 0) {
newDp[open] = dp[open - 1];
}
}
dp = newDp;
}
return dp[0];
}
}
5. Stack Method
- Iteration method involves reversing k nodes in a group iteratively.
Use a stack to track unmatched parentheses, and when encountering *, decide dynamically whether to treat it as ( or ) while maintaining balance.
- Time complexity: O(n)
- Space complexity: O(n)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkValidString(string s) {
stack left, star;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
left.push(i);
} else if (s[i] == '*') {
star.push(i);
} else {
if (left.empty() && star.empty()) return false;
if (!left.empty()) {
left.pop();
} else {
star.pop();
}
}
}
while (!left.empty() && !star.empty()) {
if (left.top() > star.top()) return false;
left.pop();
star.pop();
}
return left.empty();
}
};
Java
public class Solution {
public boolean checkValidString(String s) {
Stack left = new Stack<>();
Stack star = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(') {
left.push(i);
} else if (ch == '*') {
star.push(i);
} else {
if (left.isEmpty() && star.isEmpty()) return false;
if (!left.isEmpty()) {
left.pop();
} else{
star.pop();
}
}
}
while (!left.isEmpty() && !star.isEmpty()) {
if (left.pop() > star.pop())
return false;
}
return left.isEmpty();
}
}
Python
class Solution:
def checkValidString(self, s: str) -> bool:
left = []
star = []
for i, ch in enumerate(s):
if ch == '(':
left.append(i)
elif ch == '*':
star.append(i)
else:
if not left and not star:
return False
if left:
left.pop()
else:
star.pop()
while left and star:
if left.pop() > star.pop():
return False
return not left
JavaScript
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
checkValidString(s) {
const left = [];
const star = [];
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if (ch === '(') {
left.push(i);
} else if (ch === '*') {
star.push(i);
} else {
if (left.length === 0 && star.length === 0) {
return false;
}
if (left.length > 0) {
left.pop();
} else {
star.pop();
}
}
}
while (left.length > 0 && star.length > 0) {
if (left.pop() > star.pop()) return false;
}
return left.length === 0;
}
}
6. Greedy Method
This approach keeps track of the possible range of open parentheses using counters and adjusts them as the string is processed. It’s efficient and works without extra space.
- Time complexity: O(n)
- Space complexity: O(1)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
bool checkValidString(string s) {
int leftMin = 0, leftMax = 0;
for (char c : s) {
if (c == '(') {
leftMin++;
leftMax++;
} else if (c == ')') {
leftMin--;
leftMax--;
} else {
leftMin--;
leftMax++;
}
if (leftMax < 0) {
return false;
}
if (leftMin < 0) {
leftMin = 0;
}
}
return leftMin == 0;
}
};
Java
public class Solution {
public boolean checkValidString(String s) {
int leftMin = 0, leftMax = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
leftMin++;
leftMax++;
} else if (c == ')') {
leftMin--;
leftMax--;
} else {
leftMin--;
leftMax++;
}
if (leftMax < 0) {
return false;
}
if (leftMin < 0) {
leftMin = 0;
}
}
return leftMin == 0;
}
}
Python
class Solution:
def checkValidString(self, s: str) -> bool:
leftMin, leftMax = 0, 0
for c in s:
if c == "(":
leftMin, leftMax = leftMin + 1, leftMax + 1
elif c == ")":
leftMin, leftMax = leftMin - 1, leftMax - 1
else:
leftMin, leftMax = leftMin - 1, leftMax + 1
if leftMax < 0:
return False
if leftMin < 0:
leftMin = 0
return leftMin == 0
JavaScript
class Solution {
/**
* @param {string} s
* @return {boolean}
*/
checkValidString(s) {
let leftMin = 0;
let leftMax = 0;
for (const c of s) {
if (c === '(') {
leftMin++;
leftMax++;
} else if (c === ')') {
leftMin--;
leftMax--;
} else {
leftMin--;
leftMax++;
}
if (leftMax < 0) {
return false;
}
if (leftMin < 0) {
leftMin = 0;
}
}
return leftMin === 0;
}
}
