LeetCode-in-Java
306. Additive Number
Medium
An additive number is a string whose digits can form an additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits, return true if it is an additive number or false otherwise.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example 1:
Input: “112358”
Output: true
Explanation:
The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Example 2:
Input: “199100199”
Output: true
Explanation:
The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Constraints:
1 <= num.length <= 35numconsists only of digits.
Follow up: How would you handle overflow for very large input integers?
Solution
public class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i <= n / 2; ++i) {
for (int j = 1; Math.max(j, i) <= n - i - j; ++j) {
if (isValid(i, j, num)) {
return true;
}
}
}
return false;
}
private boolean isValid(int i, int j, String num) {
if (num.charAt(0) == '0' && i > 1) {
return false;
}
if (num.charAt(i) == '0' && j > 1) {
return false;
}
String sum;
Long x1 = Long.parseLong(num.substring(0, i));
Long x2 = Long.parseLong(num.substring(i, i + j));
for (int start = i + j; start != num.length(); start += sum.length()) {
x2 = x2 + x1;
x1 = x2 - x1;
sum = x2.toString();
if (!num.startsWith(sum, start)) {
return false;
}
}
return true;
}
}