有效的括号字符串-LeetCode [英] Valid Parenthesis String - LeetCode

问题描述

我正在通过此处链接的LeetCode来研究这个问题.

I was going through the question on LeetCode linked here.

给出一个仅包含三种类型字符的字符串:'('，')'和'*'，编写一个函数来检查该字符串是否有效.我们通过以下规则定义字符串的有效性:

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. 任何左括号'('必须具有相应的右括号')'.
2. 任何右括号')'必须具有相应的左括号'('.
3. 左括号'('必须在相应的右括号')之前.
4. '*'可被视为单个右括号')'或单个左括号'('或一个空字符串.
5. 空字符串也是有效的.

示例:

输入:(*))"

输出:是

我已经阅读了本文中指定的方法，但是我无法理解与动态编程有关的方法2 .谁能解释我们如何通过动态编程解决问题?预先感谢！

I've gone through the methods specified in the article but I'm unable to understand method 2 which is related to dynamic programming. Can anyone explain how do we need to approach the problem via dynamic programming? Thanks in advance!

主要痛点:

或者，可以将s [i]设为'('，并且[i + 1，j]中有一些k，使得s [k]可以设为')'，再加上两个间隔可以使被s [k](s [i + 1:k]和s [k + 1:j + 1])剪切的有效；

or, s[i] can be made to be '(', and there is some k in [i+1, j] such that s[k] can be made to be ')', plus the two intervals cut by s[k] (s[i+1: k] and s[k+1: j+1]) can be made valid;

推荐答案

我不确定我们可以使您共享的LeetCode链接中已经提供的解释更加清楚.针对动态程序的规定公式为

I'm not sure how much clearer we can make the explanation already offered in the LeetCode link you shared. The stated formulation for the dynamic program there is

Let dp[i][j] be true if and only if
the interval s[i], s[i+1], ..., s[j]
can be made valid.

首先要考虑的是，任何有效的括号结构都可以简化为一个独立的有效部分的组合，每个部分都具有各自的左右平衡端.例如，

First consider that any valid parenthetical construction can be reduced to a combination of self-contained valid sections, each one with their own left and right balanced ends. For example,

((()())())

在深度1处有两个内部部分:

has two inner sections at depth 1:

(valid_A valid_B)
  where valid_A is (()())
    and valid_B is ()

根据问题描述，可以将*制成一个空字符串.这将涵盖动态程序制定中的第一种情况，

According to the problem description, a * can be made into an empty string. This would cover the first case in the dynamic program formulation,

dp[i][j] is true if:
  s[i] is '*', and the interval
  s[i+1], s[i+2], ..., s[j]
  can be made valid

因为我们要查看输入中从s[i+1]到s[j]的已经有效或自包含"的部分，并且不添加任何内容(空字符串).

since we would be looking at an already valid, or "self-contained," section of the input, from s[i+1] to s[j], and adding nothing (an empty string) to it.

有效性的第二种情况是s[i]可以是(还是有效部分的开始，在这种情况下，如果我们可以在s[k]处标识其特定的平衡右括号)，我们现在可以确定的两个部分必须每个都有效，以使整个部分都有效.以前面的例子为例，

The second case for validity is if s[i] can be (, or the start of a valid section, in which case, if we can identify its specific balancing closing parenthesis, ), at s[k], the two sections we can now identify would have to each be valid in order for the whole section to be valid. To take the former example,

((()())())
 i    k j

并使用您共享的语言:

if s[i] can be made to be '(',
and there is some k in [i+1, j] such
that s[k] can be made to be ')'

我们拥有的

(()())()
i    k j

"......加上s[k](s[i+1: k]和s[k+1: j+1])切出的两个间隔...";其中s[i: j]表示间隔s[i], s[i+1], ..., s[j-1].

"...plus the two intervals cut by s[k] (s[i+1: k] and s[k+1: j+1])..."; where s[i: j] means the interval s[i], s[i+1], ..., s[j-1].

()() -> that's i+1...k-1

and

()   -> that's k+1...j

"...可以设为有效；"那么整个s[i..j]部分都是有效的.

"...can be made valid;" then the whole section s[i..j] is valid.

这篇关于有效的括号字符串-LeetCode的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！