{"id":3310,"date":"2018-07-26T21:05:58","date_gmt":"2018-07-27T04:05:58","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3310"},"modified":"2020-01-10T08:39:00","modified_gmt":"2020-01-10T16:39:00","slug":"leetcode-842-split-array-into-fibonacci-sequence","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-842-split-array-into-fibonacci-sequence\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 842. Split Array into Fibonacci Sequence"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 842. Split Array into Fibonacci Sequence - \u5237\u9898\u627e\u5de5\u4f5c EP296\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/evQCfq5wpns?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>\n<\/div><\/figure>\n\n\n<h1>Problem<\/h1>\n<p>Given a string&nbsp;<code>S<\/code>&nbsp;of digits, such as&nbsp;<code>S = \"123456579\"<\/code>, we can split it into a&nbsp;<em>Fibonacci-like sequence<\/em>&nbsp;<code>[123, 456, 579].<\/code><\/p>\n<p>Formally, a Fibonacci-like sequence is a list&nbsp;<code>F<\/code>&nbsp;of non-negative integers such that:<\/p>\n<ul>\n<li><code>0 &lt;= F[i] &lt;= 2^31 - 1<\/code>, (that is,&nbsp;each integer fits a 32-bit signed integer type);<\/li>\n<li><code>F.length &gt;= 3<\/code>;<\/li>\n<li>and<code>&nbsp;F[i] + F[i+1] = F[i+2]&nbsp;<\/code>for all&nbsp;<code>0 &lt;= i &lt; F.length - 2<\/code>.<\/li>\n<\/ul>\n<p>Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.<\/p>\n<p>Return any Fibonacci-like sequence split from&nbsp;<code>S<\/code>, or return&nbsp;<code>[]<\/code>&nbsp;if it cannot be done.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>\"123456579\"\n<strong>Output: <\/strong>[123,456,579]\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>\"11235813\"\n<strong>Output: <\/strong>[1,1,2,3,5,8,13]\n<\/pre>\n<p><strong>Example 3:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>\"112358130\"\n<strong>Output: <\/strong>[]\n<strong>Explanation: <\/strong>The task is impossible.\n<\/pre>\n<p><strong>Example 4:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>\"0123\"\n<strong>Output: <\/strong>[]\n<strong>Explanation: <\/strong>Leading zeroes are not allowed, so \"01\", \"2\", \"3\" is not valid.\n<\/pre>\n<p><strong>Example 5:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>\"1101111\"\n<strong>Output: <\/strong>[110, 1, 111]\n<strong>Explanation: <\/strong>The output [11, 0, 11, 11] would also be accepted.\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>1 &lt;= S.length&nbsp;&lt;= 200<\/code><\/li>\n<li><code>S<\/code>&nbsp;contains only digits.<\/li>\n<\/ol>\n<h1><strong>Solution: DFS<\/strong><\/h1>\n<p>Time complexity: O(2^n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\n\/\/ Running time: 0 ms \nclass Solution {\npublic:\n  vector<int> splitIntoFibonacci(string s) {\n    const int n = s.length();\n    vector<int> nums;\n    function<bool(int)> dfs = [&](int pos) {\n      if (pos == n) return nums.size() >= 3;\n      int max_len = s[pos] == '0' ? 1 : 10;\n      long num = 0;\n      for (int i = pos; i < min(pos + max_len, n); ++i) {\n        num = num * 10 + (s[i] - '0');\n        if (num > INT_MAX) break;\n        if (nums.size() >= 2) {\n          long sum = nums.rbegin()[0];\n          sum += nums.rbegin()[1];\n          if (num > sum) break;\n          else if (num < sum) continue;\n          \/\/ num must equaals to sum.\n        }\n        nums.push_back(num);\n        if (dfs(i + 1)) return true;\n        nums.pop_back();\n      }\n      return false;\n    };\n    dfs(0);\n    return nums;\n  }\n};<\/pre>\n<p>&nbsp;<\/p>","protected":false},"excerpt":{"rendered":"<p>Problem Given a string&nbsp;S&nbsp;of digits, such as&nbsp;S = &#8220;123456579&#8221;, we can split it into a&nbsp;Fibonacci-like sequence&nbsp;[123, 456, 579]. Formally, a Fibonacci-like sequence is a list&nbsp;F&nbsp;of&#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,177,348,42],"class_list":["post-3310","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-medium","tag-parition","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3310","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=3310"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3310\/revisions"}],"predecessor-version":[{"id":6063,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3310\/revisions\/6063"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}