How do you solve the Valid Parenthesis String problem using dynamic programming?

By keeping track of possible valid states as you iterate through the string, considering how each character affects the balance of parentheses and utilizing dynamic transitions.

What is the role of the wildcard '*' in the Valid Parenthesis String problem?

The wildcard '*' can represent either '(', ')', or be ignored. The solution must explore all three possibilities during the evaluation.

How can backtracking be used in this problem?

Backtracking explores all possible ways the '*' can be substituted to verify if any combination results in a valid parentheses string.

What are some common pitfalls in solving the Valid Parenthesis String problem?

Failing to handle the wildcard properly, missing potential valid configurations during backtracking, or overcomplicating the solution by not using state transitions efficiently.

What is the time complexity of solving the Valid Parenthesis String problem?

The time complexity is O(n), where n is the length of the string, as we only need to iterate through the string once.

#678

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

有效的括号字符串

给你一个只包含三种字符的字符串，支持的字符类型分别是 '(' 、 ')' 和 '*' 。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。有效字符串符合如下规则：任何左括号 '(' 必须有相应的右括号 ')' 。任何右括号 ')' 必须有相应的左括号 '(' 。左括…

字符串动态规划栈贪心

题目描述

给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

有效字符串符合如下规则：

任何左括号 '(' 必须有相应的右括号 ')'。
任何右括号 ')' 必须有相应的左括号 '(' 。
左括号 '(' 必须在对应的右括号之前 ')'。
'*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串 ""。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "(*)"
输出：true

示例 3：

输入：s = "(*))"
输出：true

提示：

1 <= s.length <= 100
s[i] 为 '('、')' 或 '*'

lightbulb

解题思路

方法一：动态规划

定义 $dp[i][j]$ 表示字符串 $s$ 中下标范围 $[i..j]$ 内的子串是否为有效括号字符串。答案为 $dp[0][n - 1]$ 。

子串长度为 $1$ 时，如果字符 $s[i]$ 为 *，则 $dp[i][i]$ 为 true，否则为 false。

子串长度大于 $1$ 时，如果满足下面任意一种情况，则 $dp[i][j]$ 为 true：

子串 $s[i..j]$ 的左边界为 ( 或 *，且右边界为 * 或 )，且 $s[i+1..j-1]$ 为有效括号字符串；
子串 $s[i..j]$ 中的任意下标 $k$ ，如果 $s[i..k]$ 为有效括号字符串，且 $s[k+1..j]$ 为有效括号字符串，则 $s[i..j]$ 为有效括号字符串。

时间复杂度 $O(n^3)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 为字符串 s 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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]

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Assess the candidate’s understanding of dynamic programming, especially in relation to state transitions.
question_mark
Evaluate how well the candidate uses backtracking to explore multiple combinations of wildcard substitutions.
question_mark
Look for the candidate's ability to optimize their approach, ensuring they don't exceed O(n) time complexity.

warning

常见陷阱

外企场景

error
Failing to account for the wildcard '*' and treating it as a fixed character can lead to incorrect solutions.
error
Not properly handling all possible states of the string during backtracking, leading to missed valid configurations.
error
Overcomplicating the solution by not leveraging efficient state transitions in dynamic programming.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to disallow the use of the wildcard '*' character.
arrow_right_alt
Implement the solution in a way that restricts the length of valid parentheses subsequences.
arrow_right_alt
Consider the problem with additional constraints such as limiting the number of wildcards or parentheses.

help

常见问题

外企场景

继续练习

#488 祖玛游戏 #402 移掉 K 位数字 #316 去除重复字母