{"id":1707,"date":"2018-01-30T23:00:21","date_gmt":"2018-01-31T07:00:21","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1707"},"modified":"2018-09-04T01:57:50","modified_gmt":"2018-09-04T08:57:50","slug":"leetcode-282-expression-add-operators","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-282-expression-add-operators\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 282. Expression Add Operators"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 282. Expression Add Operators - \u5237\u9898\u627e\u5de5\u4f5c EP163\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/v05R1OIIg08?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>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u8ba9\u4f60\u5728\u6570\u5b57\u4e4b\u95f4\u52a0\u4e0a+,-,*\u4f7f\u5f97\u7b49\u5f0f\u7684\u503c\u7b49\u4e8etarget\u3002\u8ba9\u4f60\u8f93\u51fa\u6240\u6709\u6ee1\u8db3\u6761\u4ef6\u7684\u8868\u8fbe\u5f0f\u3002<\/p>\n<p>Given a string that contains only digits\u00a0<code>0-9<\/code>\u00a0and a target value, return all possibilities to add\u00a0<b>binary<\/b>\u00a0operators (not unary)\u00a0<code>+<\/code>,\u00a0<code>-<\/code>, or\u00a0<code>*<\/code>\u00a0between the digits so they evaluate to the target value.<\/p>\n<p>Examples:<\/p>\n<pre class=\"decode-attributes:false lang:default decode:true \">\"123\", 6 -&gt; [\"1+2+3\", \"1*2*3\"] \r\n\"232\", 8 -&gt; [\"2*3+2\", \"2+3*2\"]\r\n\"105\", 5 -&gt; [\"1*0+5\",\"10-5\"]\r\n\"00\", 0 -&gt; [\"0+0\", \"0-0\", \"0*0\"]\r\n\"3456237490\", 9191 -&gt; []<\/pre>\n<p><strong>Slides:<\/strong><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1730\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-1729\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/01\/282-ep163-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<p><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\">\u00a0<\/ins><\/p>\n<h1><strong>Solution 1: DFS<\/strong><\/h1>\n<p>Time complexity: O(4^n)<\/p>\n<p>Space complexity: O(n^2) -&gt; O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 128 ms (&lt;79.97%)\r\nclass Solution {\r\npublic:\r\n  vector&lt;string&gt; addOperators(string num, int target) {\r\n    vector&lt;string&gt; ans;\r\n    dfs(num, target, 0, \"\", 0, 0, &amp;ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void dfs(const string&amp; num, const int target,  \/\/ input\r\n           int pos, const string&amp; exp, long prev, long curr, \/\/ state\r\n           vector&lt;string&gt;* ans) {  \/\/ output\r\n    if (pos == num.length()) {\r\n      if (curr == target) ans-&gt;push_back(exp);\r\n      return;\r\n    }\r\n    \r\n    for (int l = 1; l &lt;= num.size() - pos; ++l) {\r\n      string t = num.substr(pos, l);    \r\n      if (t[0] == '0' &amp;&amp; t.length() &gt; 1) break; \/\/ 0X...\r\n      long n = std::stol(t);\r\n      if (n &gt; INT_MAX) break;\r\n      if (pos == 0) {\r\n        dfs(num, target, l, t, n, n, ans);\r\n        continue;\r\n      }\r\n      dfs(num, target, pos + l, exp + '+' + t, n, curr + n, ans);\r\n      dfs(num, target, pos + l, exp + '-' + t, -n, curr - n, ans);\r\n      dfs(num, target, pos + l, exp + '*' + t, prev * n, curr - prev + prev * n, ans);\r\n    }    \r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ \/ SC O(n)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 13 ms (&lt; 99.14%)\r\nclass Solution {\r\npublic:\r\n  vector&lt;string&gt; addOperators(string num, int target) {\r\n    vector&lt;string&gt; ans;\r\n    string exp(num.length() * 2, '\\0');    \r\n    dfs(num, target, 0, exp, 0, 0, 0, &amp;ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void dfs(const string&amp; num, const int target,\r\n           int pos, string&amp; exp, int len, long prev, long curr,\r\n           vector&lt;string&gt;* ans) {    \r\n    if (pos == num.length()) {      \r\n      if (curr == target) ans-&gt;push_back(exp.substr(0, len));\r\n      return;\r\n    }\r\n    \r\n    long n = 0;\r\n    int s = pos;\r\n    int l = len;\r\n    if (s != 0) ++len;    \r\n    while (pos &lt; num.size()) {      \r\n      n = n * 10 + (num[pos] - '0');\r\n      if (num[s] == '0' &amp;&amp; pos - s &gt; 0) break; \/\/ 0X... invalid number\r\n      if (n &gt; INT_MAX) break; \/\/ too long\r\n      exp[len++] = num[pos++];\r\n      if (s == 0) {\r\n        dfs(num, target, pos, exp, len, n, n, ans);\r\n        continue;\r\n      }\r\n      exp[l] = '+'; dfs(num, target, pos, exp, len, n, curr + n, ans);\r\n      exp[l] = '-'; dfs(num, target, pos, exp, len, -n, curr - n, ans);\r\n      exp[l] = '*'; dfs(num, target, pos, exp, len, prev * n, curr - prev + prev * n, ans);\r\n    }\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 16 ms (&lt;99.17%)\r\nclass Solution {\r\n  private List&lt;String&gt; ans;\r\n  private char[] num;\r\n  private char[] exp;\r\n  private int target;\r\n  \r\n  public List&lt;String&gt; addOperators(String num, int target) {\r\n    this.num = num.toCharArray();\r\n    this.ans = new ArrayList&lt;&gt;();\r\n    this.target = target;\r\n    this.exp = new char[num.length() * 2];\r\n    dfs(0, 0, 0, 0);\r\n    return ans;\r\n  }\r\n  \r\n  private void dfs(int pos, int len, long prev, long curr) {\r\n    if (pos == num.length) {      \r\n      if (curr == target)\r\n        ans.add(new String(exp, 0, len));\r\n      return;\r\n    }\r\n    \r\n    int s = pos;\r\n    int l = len;\r\n    if (s != 0) ++len;\r\n    \r\n    long n = 0;\r\n    while (pos &lt; num.length) {\r\n      if (num[s] == '0' &amp;&amp; pos - s &gt; 0) break; \/\/ 0X...\r\n      n = n * 10 + (int)(num[pos] - '0');      \r\n      if (n &gt; Integer.MAX_VALUE) break; \/\/ too long\r\n      exp[len++] = num[pos++]; \/\/ copy exp\r\n      if (s == 0) {\r\n        dfs(pos, len, n, n);\r\n        continue;\r\n      }\r\n      exp[l] = '+'; dfs(pos, len, n, curr + n);\r\n      exp[l] = '-'; dfs(pos, len, -n, curr - n);\r\n      exp[l] = '*'; dfs(pos, len, prev * n, curr - prev + prev * n);\r\n    }\r\n  }\r\n}<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u8ba9\u4f60\u5728\u6570\u5b57\u4e4b\u95f4\u52a0\u4e0a+,-,*\u4f7f\u5f97\u7b49\u5f0f\u7684\u503c\u7b49\u4e8etarget\u3002\u8ba9\u4f60\u8f93\u51fa\u6240\u6709\u6ee1\u8db3\u6761\u4ef6\u7684\u8868\u8fbe\u5f0f\u3002 Given a string that contains only digits\u00a00-9\u00a0and a target value, return all possibilities to add\u00a0binary\u00a0operators (not unary)\u00a0+,\u00a0-, or\u00a0*\u00a0between the digits so they evaluate to&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[165,44,47],"tags":[33,173,217],"class_list":["post-1707","post","type-post","status-publish","format-standard","hentry","category-hard","category-searching","category-string","tag-dfs","tag-expression","tag-hard","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1707","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=1707"}],"version-history":[{"count":14,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1707\/revisions"}],"predecessor-version":[{"id":3850,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1707\/revisions\/3850"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1707"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1707"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1707"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}