Valid Parenthesis String with Wildcard | Dataford Interview Questions

Valid parenthesis string with wildcard *

Asked in the Data structures stage. Given a string s containing (, ), and *, determine whether it can be valid by treating each * as (, ), or an empty character.

Function: is_valid_parenthesis_string(s)

Return True if at least one interpretation is balanced, otherwise return False. A valid string has balanced parentheses, and every closing parenthesis matches an earlier opening parenthesis.

Examples: "(*)" returns True because * can be empty. "(*))" returns True because * can represent (. "())*" returns False.

Constraints

1 <= len(s) <= 10^5
s contains only '(', ')' and '*'

Function Signature

def is_valid_parenthesis_string(s):

Your question is Valid Parenthesis String with Wildcard. 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