Grokking LinkedIn Coding Interview
Ask Author
Back to course home

0% completed

Vote For New Content
Valid Parenthesis String (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a string s containing multiple occurrences of characters: '(', ')' and '*', return true if s is valid. Otherwise, return false.

A string is valid if it follows below rules:

  • Any left parenthesis '(' must be closed by corresponding right parenthesis ')'.
  • Any right parenthesis ')' must have a corresponding left parenthesis '('.
  • '*' can be used as a single left parenthesis ')' or a single right parenthesis '(' or an empty string "".

Examples

  • Example 1:

    • Input: s= "*())"
    • Expected Output: true
    • Justification: The asterisk can be treated as an open parenthesis, making the string "(())."

  • Example 2:

    • **Input: s = "((*()**"
    • Expected Output: true
    • **Justification: The first and second asterisks can be treated as close parenthesis, and the third asterisk can be treated as an empty string, resulting in a balanced set of parentheses "(()())."

  • Example 3:

    • Input: s = "())*"
    • Expected Output: false
    • Justification: There's no way to interpret the asterisk that would balance the extra close parenthesis at the start.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible