{"id":570,"date":"2017-10-09T00:26:33","date_gmt":"2017-10-09T07:26:33","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=570"},"modified":"2018-04-19T08:39:35","modified_gmt":"2018-04-19T15:39:35","slug":"leetcode-488-zuma-game","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-488-zuma-game\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 488. Zuma Game"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 488. Zuma Game - \u5237\u9898\u627e\u5de5\u4f5c EP84\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/KVlbMB7gRIk?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><a href=\"https:\/\/leetcode.com\/problems\/zuma-game\/description\/\">https:\/\/leetcode.com\/problems\/zuma-game\/description\/<\/a><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.<\/p>\n<p>Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.<\/p>\n<p>Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.<\/p>\n<p><b>Examples:<\/b><br \/>\n<b>Input:<\/b> &#8220;WRRBBW&#8221;, &#8220;RB&#8221;<br \/>\n<b>Output:<\/b> -1<br \/>\n<b>Explanation:<\/b> WRRBBW -&gt; WRR[R]BBW -&gt; WBBW -&gt; WBB[B]W -&gt; WW<\/p>\n<p><b>Input:<\/b> &#8220;WWRRBBWW&#8221;, &#8220;WRBRW&#8221;<br \/>\n<b>Output:<\/b> 2<br \/>\n<b>Explanation:<\/b> WWRRBBWW -&gt; WWRR[R]BBWW -&gt; WWBBWW -&gt; WWBB[B]WW -&gt; WWWW -&gt; empty<\/p>\n<p><b>Input:<\/b>&#8220;G&#8221;, &#8220;GGGGG&#8221;<br \/>\n<b>Output:<\/b> 2<br \/>\n<b>Explanation:<\/b> G -&gt; G[G] -&gt; GG[G] -&gt; empty<\/p>\n<p><b>Input:<\/b> &#8220;RBYYBBRRB&#8221;, &#8220;YRBGB&#8221;<br \/>\n<b>Output:<\/b> 3<br \/>\n<b>Explanation:<\/b> RBYYBBRRB -&gt; RBYY[Y]BBRRB -&gt; RBBBRRB -&gt; RRRB -&gt; B -&gt; B[B] -&gt; BB[B] -&gt; empty<\/p>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li>You may assume that the initial row of balls on the table won\u2019t have any 3 or more consecutive balls with the same color.<\/li>\n<li>The number of balls on the table won&#8217;t exceed 20, and the string represents these balls is called &#8220;board&#8221; in the input.<\/li>\n<li>The number of balls in your hand won&#8217;t exceed 5, and the string represents these balls is called &#8220;hand&#8221; in the input.<\/li>\n<li>Both input strings will be non-empty and only contain characters &#8216;R&#8217;,&#8217;Y&#8217;,&#8217;B&#8217;,&#8217;G&#8217;,&#8217;W&#8217;.<\/li>\n<\/ol>\n<p><strong>Idea:\u00a0<\/strong>Search<\/p>\n<p><strong>Solution1<\/strong>:\u00a0 C++ \/ Search<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 3 ms\r\nclass Solution {\r\npublic:\r\n    int findMinStep(string board, string hand) {\r\n        vector&lt;int&gt; h(128, 0);\r\n        for (char color : hand) ++h[color];\r\n        return dfs(board, h);\r\n    }\r\nprivate:\r\n    \/\/ Return the min # of balls needed in hand to clear the board.\r\n    \/\/ Returns -1 if not possible.\r\n    int dfs(const string&amp; board, vector&lt;int&gt;&amp; hand) {        \r\n        if (board.empty()) return 0;\r\n        \r\n        int ans = INT_MAX;\r\n        int i = 0;\r\n        int j = 0;\r\n        while (i &lt; board.size()) {\r\n            while (j &lt; board.size() &amp;&amp; board[i] == board[j]) ++j;            \r\n            \/\/ board[i] ~ board[j - 1] have the same color\r\n            const char color = board[i];\r\n            \/\/ Number of balls needed to clear board[i] ~ board[j - 1]\r\n            const int b = 3 - (j - i);\r\n            \/\/ Have sufficient balls in hand\r\n            if (hand[color] &gt;= b) {\r\n                \/\/ Remove board[i] ~ board[j - 1] and update the board\r\n                string nb = update(board.substr(0, i) + board.substr(j));\r\n                \/\/ Find the solution on new board with updated hand\r\n                hand[color] -= b;\r\n                int r = dfs(nb, hand);\r\n                if (r &gt;= 0) ans = min(ans, r + b);\r\n                \/\/ Recover the balls in hand\r\n                hand[color] += b;\r\n            }\r\n            i = j;\r\n        }\r\n        return ans == INT_MAX ? -1 : ans;\r\n    }\r\n    \r\n    \/\/ Update the board by removing all consecutive 3+ balls.\r\n    \/\/ \"YWWRRRWWYY\" -&gt; \"YWWWWYY\" -&gt; \"YYY\" -&gt; \"\"\r\n    string update(string board) {        \r\n        int i = 0;            \r\n        while (i &lt; board.size()) {\r\n            int j = i;\r\n            while (j &lt; board.size() &amp;&amp; board[i] == board[j]) ++j;\r\n            if (j - i &gt;= 3) {\r\n                board = board.substr(0, i) + board.substr(j);\r\n                i = 0;\r\n            } else {\r\n                ++i;\r\n            }\r\n        }\r\n        return board;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/zuma-game\/description\/ Problem: Think about Zuma Game. You have a row of balls on the table, colored red(R), yellow(Y), blue(B), green(G), and white(W). You also have&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,4],"class_list":["post-570","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/570","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=570"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/570\/revisions"}],"predecessor-version":[{"id":2683,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/570\/revisions\/2683"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}