DIY: Valid Parenthesis String

Solve the interview question "Valid Parenthesis String" in this lesson.

Problem statement

You are given a string named s. Your task is to find out if this string is valid. This string will only contain three type of characters i.e., (, ), and *.

A string is valid if it follows the following rules:

  • Every left ( parenthesis must have a corresponding right ) parenthesis.

  • Every right ) parenthesis must have a corresponding left ) parenthesis.

  • Every Left parenthesis ( should appear before the corresponding right ) parenthesis.

  • We can treat * as a single right or left parenthesis i.e., ( or ) or as an empty string " ".

Constraints

  • The length of the string s will be in the range [1,100].
  • Every s[i] will be either left (, or right ) parenthesis or an asterisk *.

Input

The input will be a string called s. The following are example inputs:

// Example 1
s = "()"

// Example 2
s = "(*)"

// Example 3
s = "((*)"

// Example 4
s = "(()"

Output

The output will be a boolean i.e, either true or false. The followings are sample outputs to the above inputs:

// Example 1
true

// Example 2
true

// Example 3
true

// Example 4
false

Coding exercise

You need to implement the function checkValidString(s) in the skeleton code below.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.