Press "Enter" to skip to content

花花酱 LeetCode 678. Valid Parenthesis String

Problem:

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. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid.

Example 1:

Example 2:

Example 3:

Note:

  1. The string size will be in the range [1, 100].



Idea:

Dynamic Programming / Counting

Solution 1:

C++ / DP / Top-down O(n^3)

 

C++ / DP/ Bottom-up O(n^3)

 

C++ / Counting O(n)

 

Java / DP / Bottom-up O(n^3)

 

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply