Parentheses Problems
Key Points
There are mainly 2 type problems relevant to parentheses
- Check if the parentheses in string are valid. Usually can be resolved with
stack - Generate valid parentheses in string. Usually can be resolve with
backtrack
Thinking Patterns
How to check if a string is valid parentheses?
a. The number of '(' and ')' should be same, and, b. They must be in pair. To be more specific, there should be NO leading ')', and NO open '('How to utilized stack.
a. Empty stack + ')', means leading ')' b. Non-Empty stack + the end, means open '('
An Example
Problems
| Problems | Possible Solutions | Key Points | Code | Comments |
|---|---|---|---|---|
| 20. Valid Parentheses | KP in code | type 1 | ||
| 1249. Minimum Remove to Make Valid Parentheses | Stack | code | ||
| 32. Longest Valid Parentheses | stack Dynamic Programming |
type 1 | ||
| 921. Minimum Add to Make Parentheses Valid | KP in code | type 1 | ||
| 1541. Minimum Insertions to Balance a Parentheses String | type 1 TODO: Questions in the code. |
|||
| 22. Generate Parentheses | KP in code | backtrack | type 2 | - |