
Description
The isAdditiveNumber
problem requires determining whether a given string representing a number can be split into a sequence of at least three positive numbers where each number is the sum of the two preceding ones. The function must return true
if such a sequence exists, and false
otherwise.
Intuition
An additive number sequence follows the property where each number in the sequence (starting from the third) is the sum of the two preceding numbers. The challenge is to find a valid partition of the string such that the sequence adheres to this property. A brute-force approach of testing all possible partitions and validating them can be optimized using recursion.
Approach
- Iterate Over Possible Splits:
- Loop through all possible starting pairs of numbers by splitting the string into three parts: the first number (
f
), the second number (s
), and the remaining string (l
). - Validation:
- For each split, first check if the first two numbers (
f
ands
) are valid. A number is considered valid if it does not have leading zeros unless it's "0". - Use a recursive function to validate if the rest of the string (l
) can be split into a sequence where each subsequent number is the sum of the previous two numbers. - Recursive Validation:
- If the current sum of
f
ands
matches the beginning ofl
, continue the sequence by updatingf
ands
and slicingl
accordingly. Ifl
is empty, the sequence is valid. - Edge Cases: - Handle edge cases where the number string is too short to form a sequence or contains leading zeros, which are not allowed unless the number is "0".
Complexity
Time Complexity:
The time complexity is approximately (O(n^3)), where (n) is the length of the string. This arises from the nested loops that consider every possible pair of first and second numbers and the recursive checks.
Space Complexity:
The space complexity is (O(n)) due to the recursive call stack and the space required to store intermediate substrings.
Code
C++
class Solution {
public:
bool isAdditiveNumber(string num) {
int n = num.length();
auto isValid = [](const string &str) {
return str.length() == 1 || str[0] != '0';
};
function validSeq = [&](string f, string s, string l) {
if (l.length() == 0) return true;
string sum = to_string(stoll(f) + stoll(s));
if (l.substr(0, sum.length()) != sum) return false;
return validSeq(s, sum, l.substr(sum.length()));
};
for (int i = 1; i <= n / 2; i++) {
for (int j = i + 1; j <= n - i; j++) {
string f = num.substr(0, i);
string s = num.substr(i, j - i);
string l = num.substr(j);
if (isValid(f) && isValid(s) && validSeq(f, s, l))
return true;
}
}
return false;
}
};
Python
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
def isValid(s: str) -> bool:
return len(s) == 1 or s[0] != '0'
def validSeq(f: str, s: str, l: str) -> bool:
if len(l) == 0:
return True
sum_str = str(int(f) + int(s))
if not l.startswith(sum_str):
return False
return validSeq(s, sum_str, l[len(sum_str):])
n = len(num)
for i in range(1, n // 2 + 1):
for j in range(i + 1, n - i + 1):
f, s, l = num[:i], num[i:j], num[j:]
if isValid(f) and isValid(s) and validSeq(f, s, l):
return True
return False
Java
public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; i++) {
for (int j = i + 1; j <= n - i; j++) {
String f = num.substring(0, i);
String s = num.substring(i, j);
String l = num.substring(j);
if (isValid(f) && isValid(s) && validSeq(f, s, l)) {
return true;
}
}
}
return false;
}
private boolean isValid(String str) {
return str.length() == 1 || str.charAt(0) != '0';
}
private boolean validSeq(String f, String s, String l) {
if (l.length() == 0) return true;
String sum = String.valueOf(Long.parseLong(f) + Long.parseLong(s));
if (!l.startsWith(sum)) return false;
return validSeq(s, sum, l.substring(sum.length()));
}
}
JavaScript
var isAdditiveNumber = function (num) {
const n = num.length
const isValid = (str) => {
return str.length === 1 || str[0] !== '0'
}
const validSeq = (f, s, l) => {
if (l.length === 0) return true
let sum = (parseInt(f) + parseInt(s)).toString();
for (let c = 0; c < sum.length; c++) if (sum[c] !== l[c]) return false
return validSeq(s, sum, l.slice(sum.length))
}
for (let i = 1; i <= Math.floor(n / 2); i++) {
for (let j = i + 1; j <= n - i; j++) {
let f = num.slice(0, i), s = num.slice(i, j), l = num.slice(j);
if (isValid(f) && isValid(s) && validSeq(f, s, l))
return true
}
}
return false
};