Given a string s containing only three types of characters: (, ), and *, return true if s is valid. A * can be treated as a single (, a single ), or an empty string.
Constraints: 1 ≤ s.length ≤ 100 · s[i] is '(', ')' or '*'
Given a string containing (, ), and *, determine if it can be valid. Each * can be treated as (, ), or an empty string. The question seems simple: just try each possibility and check. But how many possibilities are there?
Each star can stand for (, ), or empty string. How bad does the brute force get? Try a few assignments below and find out.
What should the star become? Try all three options.