306. Additive Number
Explanation:
To solve this problem, we can use a recursive approach where we try all possible combinations of the first two numbers and check if the rest of the string forms a valid additive sequence. We can keep track of the current numbers being considered and recursively check if the next number in the sequence is valid.
Algorithm:
- Start by iterating through all possible combinations of the first two numbers (i, j) where i ranges from 1 to num.length/2.
- For each pair (i, j), convert the substrings num[0...i] and num[i...j] to long integers and check if they have leading zeros.
- If the first two numbers are valid, check if the rest of the string forms a valid additive sequence recursively.
- In the recursive function, keep track of the current number (sum) formed by the previous two numbers and try to match it with the current prefix in the string.
- If the current prefix matches the sum, recursively check the rest of the string starting from the next index.
- If we reach the end of the string and all numbers form a valid additive sequence, return true. Otherwise, return false.
Time Complexity: O(n^3) where n is the length of the input string num. Space Complexity: O(n) for the recursive call stack.
:
class Solution {
public boolean isAdditiveNumber(String num) {
return isAdditiveNumberHelper(num, 0, 0, 0, 0);
}
private boolean isAdditiveNumberHelper(String num, int idx, long num1, long num2, int count) {
if (idx == num.length()) {
return count >= 3;
}
for (int i = idx; i < num.length(); i++) {
if (i > idx && num.charAt(idx) == '0') break;
long current = Long.parseLong(num.substring(idx, i + 1));
if (count < 2 || current == num1 + num2) {
if (isAdditiveNumberHelper(num, i + 1, num2, current, count + 1)) {
return true;
}
}
}
return false;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.