Valid Parenthesis String

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Valid Parenthesis String. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Porter route events use a compact marker string where ( represents an opening event, ) represents a closing event, and * may represent an opening event, a closing event, or no event. Given a marker string s, determine whether at least one interpretation produces a valid parenthesis sequence.

A valid sequence has balanced parentheses, every closing parenthesis matches an earlier opening parenthesis, and all parentheses are matched at the end.

Formal Specification

Implement valid_parenthesis_string(s). The input is a string containing only (, ), and *. Return True if some interpretation of every * makes s valid, otherwise return False.

Constraints

1 <= len(s) <= 100000
s contains only '(', ')' and '*'
Return a boolean result

Function Signature

def valid_parenthesis_string(s):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output