{"id":9734,"date":"2022-05-10T08:20:01","date_gmt":"2022-05-10T15:20:01","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9734"},"modified":"2022-05-10T08:25:14","modified_gmt":"2022-05-10T15:25:14","slug":"leetcode-2267-check-if-there-is-a-valid-parentheses-string-path","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-2267-check-if-there-is-a-valid-parentheses-string-path\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2267. Check if There Is a Valid Parentheses String Path"},"content":{"rendered":"\n<p>A parentheses string is a&nbsp;<strong>non-empty<\/strong>&nbsp;string consisting only of&nbsp;<code>'('<\/code>&nbsp;and&nbsp;<code>')'<\/code>. It is&nbsp;<strong>valid<\/strong>&nbsp;if&nbsp;<strong>any<\/strong>&nbsp;of the following conditions is&nbsp;<strong>true<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>It is&nbsp;<code>()<\/code>.<\/li><li>It can be written as&nbsp;<code>AB<\/code>&nbsp;(<code>A<\/code>&nbsp;concatenated with&nbsp;<code>B<\/code>), where&nbsp;<code>A<\/code>&nbsp;and&nbsp;<code>B<\/code>&nbsp;are valid parentheses strings.<\/li><li>It can be written as&nbsp;<code>(A)<\/code>, where&nbsp;<code>A<\/code>&nbsp;is a valid parentheses string.<\/li><\/ul>\n\n\n\n<p>You are given an&nbsp;<code>m x n<\/code>&nbsp;matrix of parentheses&nbsp;<code>grid<\/code>. A&nbsp;<strong>valid parentheses string path<\/strong>&nbsp;in the grid is a path satisfying&nbsp;<strong>all<\/strong>&nbsp;of the following conditions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The path starts from the upper left cell&nbsp;<code>(0, 0)<\/code>.<\/li><li>The path ends at the bottom-right cell&nbsp;<code>(m - 1, n - 1)<\/code>.<\/li><li>The path only ever moves&nbsp;<strong>down<\/strong>&nbsp;or&nbsp;<strong>right<\/strong>.<\/li><li>The resulting parentheses string formed by the path is&nbsp;<strong>valid<\/strong>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<code>true<\/code>&nbsp;<em>if there exists a&nbsp;<strong>valid parentheses string path<\/strong>&nbsp;in the grid.<\/em>&nbsp;Otherwise, return&nbsp;<code>false<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/03\/15\/example1drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[\"(\",\"(\",\"(\"],[\")\",\"(\",\")\"],[\"(\",\"(\",\")\"],[\"(\",\"(\",\")\"]]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> The above diagram shows two possible paths that form valid parentheses strings.\nThe first path shown results in the valid parentheses string \"()(())\".\nThe second path shown results in the valid parentheses string \"((()))\".\nNote that there may be other valid parentheses string paths.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2022\/03\/15\/example2drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> grid = [[\")\",\")\"],[\"(\",\"(\"]]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> The two possible paths form the parentheses strings \"))(\" and \")((\". Since neither of them are valid parentheses strings, we return false.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>m == grid.length<\/code><\/li><li><code>n == grid[i].length<\/code><\/li><li><code>1 &lt;= m, n &lt;= 100<\/code><\/li><li><code>grid[i][j]<\/code>&nbsp;is either&nbsp;<code>'('<\/code>&nbsp;or&nbsp;<code>')'<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>Let dp(i, j, b) denote whether there is a path from (i,j) to (m-1, n-1) given b open parentheses.<br>if we are at (m &#8211; 1, n &#8211; 1) and b == 0 then we found a valid path.<br>dp(i, j, b) = dp(i + 1, j, b&#8217;) or dp(i, j + 1, b&#8217;) where b&#8217; = b + 1 if  grid[i][j] == &#8216;(&#8216; else -1<\/p>\n\n\n\n<p>Time complexity: O(m*n*(m + n))<br><meta charset=\"utf-8\">Space complexity: O(m*n*(m + n))<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def hasValidPath(self, grid: List[List[str]]) -> bool:\n    m, n = len(grid), len(grid[0])    \n    \n    @cache\n    def dp(i: int, j: int, b: int) -> bool:\n      if b < 0 or i == m or j == n: return False\n      b += 1 if grid[i][j] == '(' else -1      \n      if i == m - 1 and j == n - 1 and b == 0: return True      \n      return dp(i + 1, j, b) or dp(i, j + 1, b)\n    \n    return dp(0, 0, 0)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A parentheses string is a&nbsp;non-empty&nbsp;string consisting only of&nbsp;&#8216;(&#8216;&nbsp;and&nbsp;&#8216;)&#8217;. It is&nbsp;valid&nbsp;if&nbsp;any&nbsp;of the following conditions is&nbsp;true: It is&nbsp;(). It can be written as&nbsp;AB&nbsp;(A&nbsp;concatenated with&nbsp;B), where&nbsp;A&nbsp;and&nbsp;B&nbsp;are valid parentheses&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,217,421],"class_list":["post-9734","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-parentheses","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9734","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9734"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9734\/revisions"}],"predecessor-version":[{"id":9739,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9734\/revisions\/9739"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9734"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9734"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9734"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}