{"id":483,"date":"2017-09-30T17:02:26","date_gmt":"2017-10-01T00:02:26","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=483"},"modified":"2018-04-19T08:32:07","modified_gmt":"2018-04-19T15:32:07","slug":"leetcode-678-valid-parenthesis-string","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-678-valid-parenthesis-string\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 678. Valid Parenthesis String"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 678. Valid Parenthesis String - \u5237\u9898\u627e\u5de5\u4f5c EP77\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/h9Y3i7hhCpo?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given a string containing only three types of characters: &#8216;(&#8216;, &#8216;)&#8217; and &#8216;*&#8217;, write a function to check whether this string is valid. We define the validity of a string by these rules:<\/p>\n<ol>\n<li>Any left parenthesis\u00a0<code>'('<\/code>\u00a0must have a corresponding right parenthesis\u00a0<code>')'<\/code>.<\/li>\n<li>Any right parenthesis\u00a0<code>')'<\/code>\u00a0must have a corresponding left parenthesis\u00a0<code>'('<\/code>.<\/li>\n<li>Left parenthesis\u00a0<code>'('<\/code>\u00a0must go before the corresponding right parenthesis\u00a0<code>')'<\/code>.<\/li>\n<li><code>'*'<\/code>\u00a0could be treated as a single right parenthesis\u00a0<code>')'<\/code>\u00a0or a single left parenthesis\u00a0<code>'('<\/code>\u00a0or an empty string.<\/li>\n<li>An empty string is also valid.<\/li>\n<\/ol>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">Input: \"()\"\r\nOutput: True\r\n<\/pre>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"\">Input: \"(*)\"\r\nOutput: True\r\n<\/pre>\n<p><b>Example 3:<\/b><\/p>\n<pre class=\"\">Input: \"(*))\"\r\nOutput: True\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>The string size will be in the range [1, 100].<\/li>\n<\/ol>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Dynamic Programming \/ Counting<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/678-ep78.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-485\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/678-ep78.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/678-ep78.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/678-ep78-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/678-ep78-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/678-ep78-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><strong>Solution 1:<\/strong><\/p>\n<p>C++ \/ DP \/ Top-down O(n^3)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 12 ms\r\nclass Solution {\r\npublic:\r\n    bool checkValidString(const string&amp; s) {\r\n        int l = s.length();\r\n        m_ = vector&lt;vector&lt;int&gt;&gt;(l, vector&lt;int&gt;(l, -1));\r\n        return isValid(s, 0, l - 1);\r\n    }\r\nprivate:\r\n    vector&lt;vector&lt;int&gt;&gt; m_;\r\n    bool isValid(const string&amp; s, int i, int j) {\r\n        if (i &gt; j) return true;\r\n        if (m_[i][j] &gt;= 0) return m_[i][j];        \r\n        \r\n        if (i == j) return m_[i][j] = (s[i] == '*');\r\n        \r\n        if ((s[i] == '(' || s[i] == '*')\r\n          &amp;&amp;(s[j] == ')' || s[j] == '*')\r\n          &amp;&amp; isValid(s, i + 1, j - 1))\r\n                return m_[i][j] = 1;        \r\n        \r\n        for (int p = i; p &lt; j; ++p)\r\n            if (isValid(s, i, p) &amp;&amp; isValid(s, p + 1, j))\r\n                return m_[i][j] = 1;                        \r\n        \r\n        return m_[i][j] = 0;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ DP\/ Bottom-up\u00a0O(n^3)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 12 ms\r\nclass Solution {\r\npublic:\r\n    bool checkValidString(const string&amp; s) {\r\n        int l = s.length();\r\n        if (l == 0) return true;\r\n        vector&lt;vector&lt;int&gt;&gt; dp(l, vector&lt;int&gt;(l, 0));\r\n        for (int i = 0; i &lt; l; ++i)\r\n            if (s[i] == '*') dp[i][i] = 1;\r\n        for (int len = 2; len &lt;= l; ++len)\r\n            for (int i = 0; i &lt;= l - len; ++i) {\r\n                int j = i + len - 1;\r\n                \/\/ (...), *...), (...*, *...*\r\n                if ((s[i] == '(' || s[i] == '*')\r\n                  &amp;&amp;(s[j] == ')' || s[j] == '*'))\r\n                    if (len == 2 || dp[i + 1][j - 1]) {\r\n                        dp[i][j] = 1;\r\n                        continue;                    \r\n                    }\r\n                \r\n                for (int k = i; k &lt; j; ++k)\r\n                    if (dp[i][k] &amp;&amp; dp[k + 1][j]) {\r\n                        dp[i][j] = 1;\r\n                        break;\r\n                    }\r\n            }\r\n        return dp[0][l - 1];\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>C++ \/ Counting\u00a0O(n)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 3 ms\r\nclass Solution {\r\npublic:\r\n    bool checkValidString(string s) {\r\n        int min_op = 0;\r\n        int max_op = 0;\r\n        \r\n        for (char c : s) {\r\n            if (c == '(') ++min_op; else --min_op;\r\n            if (c != ')') ++max_op; else --max_op;\r\n            if (max_op &lt; 0) return false;\r\n            min_op = max(0, min_op);\r\n        }\r\n        \r\n        return min_op == 0;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>Java \/ DP \/ Bottom-up O(n^3)<\/p>\n<pre class=\"lang:java decode:true \">class Solution {\r\n    public boolean checkValidString(String s) {\r\n        int l = s.length();\r\n        if (l == 0) return true;\r\n        boolean[][] dp = new boolean[l][l];\r\n        \r\n        char[] ss = s.toCharArray();\r\n        for (int i = 0; i &lt; l; ++i)\r\n            if (ss[i] == '*') dp[i][i] = true;\r\n        for (int len = 2; len &lt;= l; ++len)\r\n            for (int i = 0; i + len &lt;= l; ++i) {\r\n                int j = i + len - 1;\r\n                \r\n                if ((ss[i] == '*' || ss[i] == '(')\r\n                  &amp;&amp;(ss[j] == '*' || ss[j] == ')')) {\r\n                    if (len == 2 || dp[i + 1][j - 1]) {\r\n                        dp[i][j] = true;\r\n                        continue;\r\n                    }\r\n                }\r\n                \r\n                for (int k = i; k &lt; j; ++k)\r\n                    if (dp[i][k] &amp;&amp; dp[k + 1][j]) {\r\n                        dp[i][j] = true;\r\n                        break;\r\n                    }\r\n            }\r\n        \r\n        return dp[0][l - 1];\r\n    }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Given a string containing only three types of characters: &#8216;(&#8216;, &#8216;)&#8217; and &#8216;*&#8217;, write a function to check whether this string is valid. We&#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":[20,8,4],"class_list":["post-483","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-array","tag-counting","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/483","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=483"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/483\/revisions"}],"predecessor-version":[{"id":2582,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/483\/revisions\/2582"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=483"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=483"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=483"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}