Sponsored
Sponsored
This approach uses backtracking to recursively split the string into all potential combinations of integers and checks if they form a valid Fibonacci sequence.
Time Complexity: O(2^n), since each combination of splitting points is considered recursively.
Space Complexity: O(n), for the recursion stack and the result list.
1function splitIntoFibonacci(S) {
2 const result = [];
3
4 function backtrack(index) {
5 if (index === S.length) return result.length >= 3;
6
7 let currentNumber = 0;
8 for (let i = index; i < S.length; i++) {
9 if (i > index && S[index] === '0') break;
10 currentNumber = currentNumber * 10 + (S[i] - '0');
11 if (currentNumber > Math.pow(2, 31) - 1) break;
12
13 if (result.length < 2 || currentNumber === result[result.length - 1] + result[result.length - 2]) {
14 result.push(currentNumber);
15 if (backtrack(i + 1)) return true;
16 result.pop();
17 }
18 }
19 return false;
20 }
21
22 return backtrack(0) ? result : [];
23}This JavaScript code employs a recursive backtracking technique to find Fibonacci-like sequences in a string.
backtrack function orchestrates the recursive exploration of valid sequences.This approach involves iteratively parsing possible substrings and dynamically checking for valid Fibonacci sequences.
Time Complexity: O(n^3), due to nested loops exploring potential splits and sequence validity.
Space Complexity: O(n), primarily to store intermediate sequence results.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
public IList<int> SplitIntoFibonacci(string S) {
var result = new List<int>();
for (int i = 0; i < S.Length - 2; i++) {
if (i > 0 && S[0] == '0') break;
long a = long.Parse(S.Substring(0, i + 1));
if (a > int.MaxValue) break;
result.Add((int)a);
for (int j = i + 1; j < S.Length - 1; j++) {
if (j > i + 1 && S[i + 1] == '0') break;
long b = long.Parse(S.Substring(i + 1, j + 1 - (i + 1)));
if (b > int.MaxValue) break;
result.Add((int)b);
if (IsValid(S.Substring(j + 1), result)) return result;
result.RemoveAt(result.Count - 1);
}
result.RemoveAt(result.Count - 1);
}
return new List<int>();
}
private bool IsValid(string S, List<int> result) {
int n1 = result[result.Count - 2];
int n2 = result[result.Count - 1];
for (int k = 0; k < S.Length; k++) {
long next = (long)n1 + n2;
if (next > int.MaxValue) return false;
string nextString = next.ToString();
if (!S.StartsWith(nextString)) return false;
n1 = n2;
n2 = (int)next;
k += nextString.Length - 1;
}
return true;
}
}This C# approach uses similar logic to the Java solution for iterative Fibonacci sequence generation.