678. Valid Parenthesis String

A star is not a wildcard you resolve on the spot. The moment you try to decide what each * becomes while scanning, you are guessing, and guessing costs you 3^n branches. The decision has to be deferred until the whole string is on the table.