★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址：  

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

• 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
• F.length >= 3;
• and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

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.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"Output: [123,456,579]

Example 2:

Input: "11235813"Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"Output: []Explanation: The task is impossible.

Example 4:

Input: "0123"Output: []Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"Output: [110, 1, 111]Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1. 1 <= S.length <= 200
2. S contains only digits.

---

给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。

形式上，斐波那契式序列是一个非负整数列表 F，且满足：

• 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
• F.length >= 3；
• 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2]成立。

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 S 拆分出来的所有斐波那契式的序列块，如果不能拆分则返回 []。

示例 1：

输入："123456579"输出：[123,456,579]

示例 2：

输入: "11235813"输出: [1,1,2,3,5,8,13]

示例 3：

输入: "112358130"输出: []解释: 这项任务无法完成。

示例 4：

输入："0123"输出：[]解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

示例 5：

输入: "1101111"输出: [110, 1, 111]解释: 输出 [11,0,11,11] 也同样被接受。

提示：

1. 1 <= S.length <= 200
2. 字符串 S 中只含有数字。

---

8ms

1 class Solution { 2     fileprivate var res = [Int]() 3     fileprivate var maxVal = Int(pow(2.0,31.0)-1) 4     fileprivate var found = false 5      6     func splitIntoFibonacci(_ S: String) -> [Int] { 7         guard S.count >= 3 else { 8             return [Int]() 9         }10         11         var S = S.characters.map{Int(String($0))!}12         13         findSequence(S)14         return found ? res : [Int]()15     }16     17     func findSequence(_ S: [Int], _ from: Int = 0){18         if from >= S.count && res.count >= 3{19             found = true20             return21         }22     23         var current = 024         for i in from..
     
      = 1 && current < 10{32                 return33             }34             35             if isFibSeq(current){36                 findSequence(S, i + 1)37                 if found{38                     return39                 }40                 res.remove(at: res.count - 1)41             }42         }43     }44     45     func isFibSeq(_ num: Int)->Bool{46         let count = res.count47         if count < 2{48             res.append(num)49             return true50         }51         52         if res[count - 1] + res[count - 2] == num{53             res.append(num)54             return true55         }56         57         return false58     }59 }
     

---

20ms

1 private extension String { 2     var leadingZero: Bool { 3         guard self.count > 1 else { 4             return false 5         } 6  7         if self[self.startIndex] == "0" { 8             return true 9         }10 11         return false12     }13 }14 15 /// 我们将一个给定的字符串进行分割，分割成斐波那契数列16 17 class Solution {18     var limit: Int = 2_147_483_64719 20     func splitIntoFibonacci(_ S: String) -> [Int] {21         if S.count < 3 {22             return []23         }24         var array: [String] = []25 26         for index in 1...(min(10, S.count - 2)) {27             let firstString = String(S.prefix(index))28 29             let lastString = String(S.suffix(S.count - index))30 31             array.append(firstString)32 33             if firstString.leadingZero {34                 return []35             }36 37             if findSecondSecondString(String(lastString), list: &array) {38                 return array.map({Int($0) ?? 0})39             } else {40                 array.removeAll()41             }42         }43 44         return []45     }46 47     func findSecondSecondString(_ S: String, list: inout [String]) -> Bool {48         if S.count  < 1 {49             return false50         }51 52         for index in 1...(min(10, S.count - 1)) {53             let firstString = String(S.prefix(index))54 55             let lastString = String(S.suffix(S.count - index))56 57             list.append(firstString)58 59             if judgeStringCanUse(lastString, list: &list) {60                 return true61             } else {62                 let keep = list[0]63                 list.removeAll()64                 list.append(keep)65                 continue66             }67         }68         return false69     }70 71     func judgeStringCanUse(_ S: String, list: inout [String]) -> Bool {72         if S.count == 0 && list.count > 2 {73             return true74         }75 76         let n = Int(list[list.count - 1]) ?? 077         let n1 = Int(list[list.count - 2]) ?? 078         let target = n + n179         guard n <= limit && n1 <= limit && target <= limit else {80             return false81         }82 83         let targetString = "\(n + n1)"84 85         let firstS = S.prefix(targetString.count)86 87         if firstS == targetString {88             list.append(String(firstS))89 90             return judgeStringCanUse(String(S.suffix(S.count - firstS.count)), list: &list)91         }92 93         return false94     }95 }

---

Runtime: 36 ms

Memory Usage: 21.8 MB

1 class Solution { 2     func splitIntoFibonacci(_ S: String) -> [Int] { 3         var ans:[Int] = [Int]() 4         var cur:[Int] = [Int]() 5         if S.isEmpty {
    return ans} 6         SFhelper(S,0,&cur,&ans) 7         return ans 8     } 9     10     func SFhelper(_ S:String,_ start:Int,_ cur:inout [Int],_ ans:inout [Int])11     {12         if !ans.isEmpty{
    return}13         if start == S.count14         {15             if cur.count > 2 { ans += cur}16             return17         }18         let N:Int = cur.count19         var V:Int64 = 020         var arrS:[Character] = Array(S)21         for i in start..
      
        2147483647 {
    break}25             if N < 226             {27                 cur.append(Int(V))28                 SFhelper(S, i + 1, &cur, &ans)29                 cur.popLast()30             }31             else32             {33                 let beforeSum:Int = cur[N - 1] + cur[N - 2]34                 if beforeSum > V {
    continue}35                 else if beforeSum < V {
    break}36                 else37                 {38                     cur.append(Int(V))39                     SFhelper(S, i + 1, &cur, &ans)40                     cur.popLast()41                 }42             }43              if V==0 {
    break}44         }45     }46 }47 48 //Character扩展49 extension Character50 {51     //Character转ASCII整数值(定义小写为整数值)52     var ascii: Int {53         get {54             return Int(self.unicodeScalars.first?.value ?? 0)55         }56     }57 }
      

---

100ms

1 class Solution { 2     private var result: [Int] = [] 3     func splitIntoFibonacci(_ S: String) -> [Int] { 4         split(Array(S), nil, nil, nil, 0, []) 5         return result 6     } 7      8     private func split(_ s: [Character], 9                        _ op1: Int?,10                        _ op2: Int?,11                        _ sum: Int?,12                        _ start: Int,13                        _ out: [Int]) -> Bool {14         if start == s.count {15             if op1 != nil && op2 != nil && sum != nil {16                 result = out17                 return true 18             }19             return false 20         } else {21             for i in start..
      
        0 && s[start] == "0" { return false }23                 if let num = String(s[start...i]).toInt() {24                     if num > Int(pow(2.0, 31.0)) - 1 { return false }25                     if op1 == nil {26                         if split(s, num, op2, sum, i + 1, out + [num]) {27                             return true 28                         }29                     } else if op2 == nil {30                         if split(s, op1, num, sum, i + 1, out + [num]) {31                             return true 32                         }33                     } else {34                         if num - op1! == op2! {35                             if split(s, op2, num, num, i + 1, out + [num]) {36                                 return true 37                             }38                         }39                     }40                 }41             }42               return false43         }44     }45 }46 47 extension String {48     func toInt() -> Int? {49         return Int(self)!50     }51 }
      

---

104ms

1 class Solution { 2     func splitIntoFibonacci(_ S: String) -> [Int] { 3         var result = [Int]() 4         var chars = Array(S) 5         helper(&result, chars) 6         return result 7     } 8      9     fileprivate func helper(_ res: inout [Int], _ chars: [Character]) -> Bool {10         if res.count > 2 && chars.count == 0 {11             return true12         }13         14         for i in 0..
      
        0 {16                 break17             }18             19             // Int("2147483647214748364")!20             21             guard let val = Int(String(chars[0...i])), val < Int32.max else {22                 return false23             }24             25             26             let size = res.count27             if size >= 2 && val > res[size - 1] + res[size - 2] {28                 return false29             }30 31             if size < 2 || val == res[size - 1] + res[size - 2] {32                 res.append(val)33                 if helper(&res, Array(chars[(i+1)...])) {34                     return true35                 }36                 res.removeLast()37             }38         }39         return false;40     }41 }