Algorithm

Problem Name: 678. Valid Parenthesis String

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 `""`.

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 `'*'`.

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean checkValidString(String s) {
int low = 0;
int high = 0;
for (char c : s.toCharArray()) {
low += c == '(' ? 1 : -1;
high += c != ')' ? 1 : -1;
if (high  <  0) {
break;
}
low = Math.max(low, 0);
}
return low == 0;
}
}
``````
Copy The Code &

Input

cmd
s = "()"

Output

cmd
true

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const checkValidString = function(s) {
let lo = 0, hi = 0;
for (let i = 0; i  <  s.length; i++) {
lo += s[i] == '(' ? 1 : -1;
hi += s[i] != ')' ? 1 : -1;
if (hi  <  0) break;
lo = Math.max(lo, 0);
}
return lo === 0;
};
``````
Copy The Code &

Input

cmd
s = "()"

Output

cmd
true

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
left, left_star = [], []
for i in range(len(s)):
if s[i] == "(": left.append([s[i], i])
elif s[i] == "*": left_star.append([s[i], i])
elif left and left[-1][0] == "(": left.pop()
elif left_star: left_star.pop()
else: return False
while left and left_star and left[-1][1]< left_star[-1][1]: left.pop(); left_star.pop()
return not left
``````
Copy The Code &

Input

cmd
s = "(*)"

Output

cmd
true

#4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0678_ValidParenthesisString
{
public bool CheckValidString(string s)
{
var lo = 0;
var hi = 0;
foreach (var ch in s)
{
lo += ch == '(' ? 1 : -1;
hi += ch != ')' ? 1 : -1;
if (hi  <  0) return false;
lo = Math.Max(lo, 0);
}

return lo == 0;
}
}
}
``````
Copy The Code &

Input

cmd
s = "(*)"

Output

cmd
true