306. Additive Number #

Problem #

Additive number is a string whose digits can form 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 '0'-'9', write a function to determine if it’s an additive number.

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

Follow up:How would you handle overflow for very large input integers?

Problem Summary #

An additive number is a string whose digits can form an additive sequence. A valid additive sequence must contain at least 3 numbers. Except for the first two numbers, every other number in the string must be equal to the sum of the two numbers before it. Given a string containing only digits ‘0’-‘9’, write an algorithm to determine whether the given input is an additive number. Note: Numbers in the additive sequence will not start with 0, so cases like 1, 2, 03 or 1, 02, 3 will not occur.

Solution Approach #

Determine whether the given string is a string in the form of a Fibonacci sequence.
Since each check needs to add 2 numbers, during DFS traversal we need to maintain the boundaries of 2 numbers, firstEnd and secondEnd; the starting position of the sum of the two numbers is secondEnd + 1. Each time firstEnd and secondEnd are moved, we need to check strings.HasPrefix(num[secondEnd + 1:], strconv.Itoa(x1 + x2)), that is, whether the following string starts with the sum.
If the starting digit of the first number is 0, or the starting digit of the second number is 0, both are invalid exceptional cases and should directly return false.

Code #


package leetcode

import (
	"strconv"
	"strings"
)

// This function controls various combinations as starting points
func isAdditiveNumber(num string) bool {
	if len(num) < 3 {
		return false
	}
	for firstEnd := 0; firstEnd < len(num)/2; firstEnd++ {
		if num[0] == '0' && firstEnd > 0 {
			break
		}
		first, _ := strconv.Atoi(num[:firstEnd+1])
		for secondEnd := firstEnd + 1; max(firstEnd, secondEnd-firstEnd) <= len(num)-secondEnd; secondEnd++ {
			if num[firstEnd+1] == '0' && secondEnd-firstEnd > 1 {
				break
			}
			second, _ := strconv.Atoi(num[firstEnd+1 : secondEnd+1])
			if recursiveCheck(num, first, second, secondEnd+1) {
				return true
			}
		}
	}
	return false
}

//Propagate for rest of the string
func recursiveCheck(num string, x1 int, x2 int, left int) bool {
	if left == len(num) {
		return true
	}
	if strings.HasPrefix(num[left:], strconv.Itoa(x1+x2)) {
		return recursiveCheck(num, x2, x1+x2, left+len(strconv.Itoa(x1+x2)))
	}
	return false
}