title: Valid Parenthesis String - LeetCode
body: <p>I was going through the question on LeetCode linked <a href="https://leetcode.com/articles/valid-parenthesis-string/" rel="nofollow noreferrer">here</a>.</p>
  
  <p>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:</p>
  
  <ol>
  <li>Any left parenthesis '(' must have a corresponding right parenthesis ')'.</li>
  <li>Any right parenthesis ')' must have a corresponding left parenthesis '('.</li>
  <li>Left parenthesis '(' must go before the corresponding right parenthesis ')'.</li>
  <li>'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.</li>
  <li>An empty string is also valid.</li>
  </ol>
  
  <blockquote>
    <p><strong>Example:</strong></p>
    
    <p><strong>Input:</strong> "(*))"</p>
    
    <p><strong>Output:</strong> True</p>
  </blockquote>
  
  <p>I've gone through the methods specified in the article but I'm unable to understand <strong>method 2</strong> which is related to <strong>dynamic programming</strong>. Can anyone explain how do we need to approach the problem via dynamic programming? Thanks in advance!</p>
  
  <p>Main pain point:</p>
  
  <blockquote>
    <p>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;</p>
  </blockquote>