Algorithm
Problem Name: 678. Valid Parenthesis String
Problem Link: https://leetcode.com/problems/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 <= 100s[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;
}
}
Input
s = "()"
Output
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;
};
Input
s = "()"
Output
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
Input
s = "(*)"
Output
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;
}
}
}
Input
s = "(*)"
Output
true