842. Split Array into Fibonacci Sequence
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Solution {
long toInt(string s) {
long res = 0;
for(int i = 0; i < s.length(); i++) {
res = (res<<3) + (res<<1) + (s[i] & 0b1111);
}
return res;
}
bool invalid(string s) {
return s.length() >= 2 && s[0] == '0';
}
bool equal(int sum, string& s, int& pos) {
string target = to_string(sum);
if(target.length() + pos > s.length()) return false;
for(auto& c : target) {
if(s[pos++] != c) return false;
}
return true;
}
public:
vector<int> splitIntoFibonacci(string S) {
vector<int> res;
int len = S.length();
stringstream f1;
for(int i = 0; i < len / 2; i++) {
f1 << S[i];
stringstream f2;
long f1L = toInt(f1.str());
if(invalid(f1.str()) || f1L > INT_MAX) return vector<int>();
for(int j = i + 1; j + i < len; j++) {
f2 << S[j];
long f2L = toInt(f2.str());
if(invalid(f2.str()) || f2L > INT_MAX) break;
int pos = j + 1;
res.clear();
res.push_back(f1L);
res.push_back(f2L);
while(pos < len) {
long sum = 1L * (*prev(res.end())) + 1L * (*prev(prev(res.end())));
if(sum <= INT_MAX && equal(sum, S, pos)) res.push_back(sum);
else {pos = -1; break; }
}
if(pos == len) return res;
}
}
return vector<int>();
}
};
|
