Problem Breakdown
We are given a string S consisting of digits and need to partition it into a sequence of non-negative integers such that:
- Length Constraint: The sequence must have at least 3 numbers ().
- Value Constraint: Each number fits within a signed 32-bit integer (
0 <= F[i] <= 2^31 - 1). - Recurrence Relation: for all valid indices (standard Fibonacci property).
- Formatting Constraint: No leading zeros allowed unless the number is exactly “0”.
Inputs & Outputs:
- Input: String
Sof digits, length up to 200. - Output: A list of integers forming a valid sequence or an empty list if impossible.
Tricky Edge Cases:
- Leading Zeros: Splitting “10” into [“1”, “0”] is fine (if part of seq), but splitting “05” as [“0”, “5”] is invalid because the second number has a leading zero in this context? Wait, Example 4 says
S="0123"-> Output[[]]. Explanation: Leading zeroes not allowed. So if we split at index 1 (“0”), next starts with ‘1’. But wait, [“0”, “1”] is valid for the numbers themselves (single digit zero). However, splitting “0” and then “1”? The issue in Example 4 is likely thatS="0123"implies if we take first num as “0”, second must be from remaining. If we split at index 1 (“0”), next starts with ‘1’. But wait, the example output says[[]]. Why? Because after taking “0” and “1”, sum is 1. Next char in S is ‘2’, expected ‘1’. Mismatch.- Actually, Example 4 explanation:
S="0123"-> Output[]because leading zeroes are not allowed for multi-digit numbers? No, it says"01", “2”, “3” is invalid. This refers to the number formed by a substring starting with ‘0’ having length > 1. - So if we parse a substring like “05”, that’s invalid immediately. If we parse “0”, valid (value 0).
- Actually, Example 4 explanation:
Intuition
A brute-force approach would try every possible partition of S into numbers and check the Fibonacci property, which is exponential in terms of number count ( or worse) because there are many ways to split a string. However, we can optimize this observation:
- Deterministic Future: Once the first two numbers (
a,b) are chosen from the start ofS, every subsequent number is mathematically determined (). We do not need backtracking for . - Search Space Reduction: The only degrees of freedom we have to explore are the lengths (split points) of the first two numbers,
aandb. Since each number must fit in a signed 32-bit integer ( digits), the loop for split points doesn’t need to go all the way to , but practically we can iterate valid substring lengths. - Validation: For every pair of initial numbers, we simulate generating the rest of the sequence against
S. If a mismatch occurs or an integer limit is exceeded at any step, that specific split point for(a, b)fails immediately.
Approach
- Initial Checks: Return empty list if string length .
- Iterate First Number (
a): Loop through possible end indicesi. Extract substringS[0:i]. Check validity (no leading zeros unless “0”). Parse to integer, check against MAX_INT (). If valid, store asnum_a. - Iterate Second Number (
b): Loop through possible end indicesj > i. Extract substringS[i:j]. Check validity (no leading zeros unless “0”). Parse to integer, check against MAX_INT. If valid, store asnum_b. - Simulation: With fixed
aandb, iterate forward:- Calculate expected next value =
a + b. - Check if the remaining string starts with this number’s digits.
- Update pointers (
imoves past current match). - Shift window so new numbers become previous two for sum calculation.
- Calculate expected next value =
- Success Condition: If simulation consumes exactly all characters in
S, return the sequence list. - Failure Handling: If loop finishes without success, try next split points.
Complexity Analysis
- Time Complexity: where is string length and is max digits per number (bounded by integer limit ). Effectively roughly constant iterations for the outer loops ( or valid lengths) multiplied by a linear scan of
Sduring simulation. Given constraints, this behaves close to in practice because we prune invalid splits early (overflow/leading zero checks). - Space Complexity: auxiliary space excluding the output list storage ( where is sequence length), as we only store pointers and current numbers.
Solution
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
n = len(S)
if n < 3:
return []
MAX_INT = (1 << 31) - 1
# Iterate over the length of the first number 'a'
for i in range(1, min(n // 2 + 1, n)):
# Optimization: If substring is too long to fit int or has leading zero issues
a_str = S[:i]
# Check leading zeros constraint (only "0" allowed if len > 1)
if i > 1 and a_str[0] == '0':
continue
try:
num_a = int(a_str)
except ValueError:
continue
# If number exceeds signed 32-bit integer limit, this split is invalid.
# Note: Python handles large ints automatically, so we must check value manually.
if num_a > MAX_INT:
break
# Iterate over the length of the second number 'b' starting after first number ends
for j in range(i + 1, min(n - i // 2 + 1, n)):
b_str = S[i:j]
if len(b_str) > 9: # Optimization check based on max int digits roughly
break
# Check leading zeros constraint
if (j - i) > 1 and b_str[0] == '0':
continue
try:
num_b = int(b_str)
except ValueError:
continue
if num_b > MAX_INT:
break
# Simulation phase with fixed a and b
curr_a, curr_b = num_a, num_b
idx = j # Current pointer in S after second number ends
result = [curr_a, curr_b]
while True:
expected_sum = curr_a + curr_b
if idx >= n or len(S) - idx < len(str(expected_sum)):
break
next_str = S[idx : idx + len(str(expected_sum))]
# Check for leading zero in the generated substring (if it's not just "0")
# Actually, we must ensure that the slice matches exactly.
# If expected_sum is 0 and string starts with '0', valid? Yes if single digit.
# But wait, S[idx] could be part of a larger number in input logic? No, next_str MUST match str(expected_sum)
if idx + len(str(expected_sum)) > n:
break
current_sub = S[idx : idx + len(str(expected_sum))]
# Check leading zero on the substring we just matched from string (if it's not single 0)
# Actually, since expected_sum is derived mathematically, if str(expected_sum) has no leading zeros
# and matches current_sub, then current_sub also won't have them.
# However, we must ensure that the substring in S doesn't imply a different split?
# No, because Fibonacci property forces exact match of value. If S[idx] starts with '0' but expected_sum != 0, mismatch.
if len(current_sub) > 1 and current_sub[0] == '0':
break
if next_str != str(expected_sum):
# Mismatch in digits or length?
# We check exact match of substring to string representation
pass
# Correct logic: Check if S[idx : idx + len(str(sum))] equals str(sum)
sub_len = len(str(expected_sum))
if idx + sub_len > n: break
actual_sub = S[idx : idx + sub_len]
if actual_sub != str(expected_sum):
# Mismatch, this pair (a,b) is invalid for the rest of string
curr_a, curr_b = num_a, num_b
result = [curr_a, curr_b]
break
# Update pointers and values
idx += sub_len
curr_a, curr_b = curr_b, expected_sum
if len(result) == 0: pass # Just appending logic below
else:
continue # Continue outer loop on next split attempt? No.
return result
```python
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
n = len(S)
if n < 3:
return []
MAX_INT = (1 << 31) - 1
# Iterate over the length of the first number 'a'
for i in range(1, min(n // 2 + 1, n)):
a_str = S[:i]
if len(a_str) > 9: break
if len(a_str) > 1 and a_str[0] == '0': continue
num_a = int(a_str)
if num_a > MAX_INT: break
# Iterate over the length of the second number 'b' starting after first number ends
for j in range(i + 1, min(n - i // 2 + 1, n)):
b_len = len(S[i:j])
if b_len > 9: break
if (j - i) > 1 and S[i] == '0': continue
num_b = int(S[i:j])
if num_b > MAX_INT: break
# Simulation phase with fixed a and b
curr_a, curr_b = num_a, num_b
idx = j
result = [curr_a, curr_b]
while True:
expected_sum = curr_a + curr_b
if idx >= n or len(S) - idx < len(str(expected_sum)):
break
sub_len = len(str(expected_sum))
# Check leading zero constraint on the matched substring from S (if not single 0)
actual_sub = S[idx : idx + sub_len]
if len(actual_sub) > 1 and actual_sub[0] == '0': break
if actual_sub != str(expected_sum):
curr_a, curr_b = num_a, num_b
result = [curr_a, curr_b] # Reset for next iteration? No. Break simulation loop to try next split pair.
break
idx += sub_len
curr_a, curr_b = curr_b, expected_sum
if idx == n: return result
return []
```python
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
n = len(S)
if n < 3: