MediumNo. 0678
Valid Parenthesis String — LeetCode 678 Python Solution
- Pattern
- Stack
- Topics
- Stack, Greedy, String, Dynamic Programming
- On a study list
- NeetCode 150
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid. The following rules define a valid string: Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Example
- Input
- s = "()"
- Output
- true
Python solution
class Solution:
def checkValidString(self, s: str) -> bool:
n = len(s)
dp = [[False] * n for _ in range(n)]
for i, c in enumerate(s):
dp[i][i] = c == '*'
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
dp[i][j] = (
s[i] in '(*' and s[j] in '*)' and (i + 1 == j or dp[i + 1][j - 1])
)
dp[i][j] = dp[i][j] or any(
dp[i][k] and dp[k + 1][j] for k in range(i, j)
)
return dp[0][-1]Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 678. Valid Parenthesis String is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2645 | Minimum Additions to Make Valid String | Medium |
| 0032 | Longest Valid Parentheses | Hard |
| 0044 | Wildcard Matching | Hard |
| 0488 | Zuma Game | Hard |
| 1130 | Minimum Cost Tree From Leaf Values | Medium |
| 1526 | Minimum Number of Increments on Subarrays to Form a Target Array | Hard |
Frequently asked questions
- How hard is LeetCode 678. Valid Parenthesis String?
LeetCode 678. Valid Parenthesis String is rated Medium on LeetCode.
- What topics does LeetCode 678. Valid Parenthesis String cover?
LeetCode 678. Valid Parenthesis String is tagged Stack, Greedy, String and Dynamic Programming on LeetCode.