Valid Parenthesis String | Dataford Interview Questions

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 question is Valid Parenthesis String. Start with the requirements in the Question tab.

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

Problem