Show problems as
Classic problem #678MediumStringDynamic ProgrammingStackGreedyBracket Sequences

Valid Parenthesis String

Real-world version: Salvage a Smudged Span Trace
Tracked in this browser only
Read Valid Parenthesis String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A packaging tool records a trace while it walks a project. It writes ( when it enters a span and ) when it leaves one, and a leaving mark always settles the span that was entered most recently and is still open. A trace is sound when every leaving mark settles some earlier entering mark and no span is left open once the trace runs out.

One run wrote to a failing disk, so a few bytes came back smudged. A smudged byte is recorded as *, and each one may have held an entering mark, a leaving mark, or no mark at all. Two smudged bytes need not be read the same way.

You are handed the recovered trace s. Return true when at least one reading of the smudged bytes leaves a sound trace, and false when no reading does.

Examples

Example 1

Input
s = "((**))"
Output
true

Read both smudged bytes as carrying no mark and the trace becomes two entering marks followed by two leaving marks, which is sound.

Example 2

Input
s = "*)(("
Output
false

The trace finishes with two entering marks and nothing after them, so two spans stay open no matter how the leading smudge is read.

Example 3

Input
s = "**"
Output
true

Reading both bytes as carrying no mark leaves an empty trace, which is sound; reading the first as entering and the second as leaving works too.

Constraints

  • 1 <= s.length <= 100
  • Every character of `s` is `(`, `)` or `*`.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def trace_is_recoverable(s: str) -> bool:
Java
public boolean traceIsRecoverable(String s)

More on the same topics