Problem#
給你一個字串 s 其中只包含三種字元: (, ), *，所有的括號必須左右匹配，右括號必須在左括號後面，星號可以變成左、右括號、或空字串，回傳字串 s 是否合法。
測資限制#
- $1 \le n \le 100$
想法#
掃過一次 s，如果遇到 ( 或 * 則記錄位置，接著如果遇到 ) 先看能不能和 ( 配對，如果不行再看能不能和 * 配對，如果都不行則代表字串 s 不合法。
掃完字串後，先前紀錄的 ( 如果沒有配對完，則要看剩下的 * 能不能全部配對完，配對的前提是: * 必須出現在 ( 之後(替代 ))，如果不能配對完，則代表不合法；反之則合法。
AC Code#
- 時間複雜度: $\mathcal{O}(n)$
- 空間複雜度: $\mathcal{O}(n)$
賞析#
TODO 官方題解 DP