枚举序列的前两个位数字,再用dfs递归判断字符串接下来的数字是否等于A+B。要注意字符串转INT的边界情况。
const int N = 210;
class Solution {
public:
vector<int> ans;
int n;
int len_max = to_string(INT_MAX).length();
int getVal(string &str, int start, int end){
int len = end - start + 1;
if (end > str.size() || len > len_max) return -1;
if (len > 1 && str[start] == '0') return -1;
auto ret = stol(str.substr(start, len));
if (ret > INT_MAX) return -1;
return (int) ret;
}
bool dfs(string &S, int start, int last, long goal){
if (start == n)
return true;
int end = to_string(goal).length() + start - 1;
int x = getVal(S, start, end);
if (x == goal){
ans.push_back(x);
if (dfs(S, end+1, x, (long)last + x)) return true;
ans.pop_back();
}
return false;
}
vector<int> splitIntoFibonacci(string S) {
n = S.size();
ans.resize(2);
for (int i =1; i<n; i++){
int a = getVal(S, 0, i-1);
if (a == -1) break;
for (int j = i; j<n; j++){
int b = getVal(S, i, j);
if (b == -1) break;
ans[0] = a, ans[1] = b;
if (dfs(S, j+1, b, (long) a + b))
return ans;
}
}
return {};
}
};