LeetCode Q306: Additive Number

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.

For example:
"112358" is an additive number because 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

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

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

Solution:

Need to take care of many details for example: the number can be '0', but can not be one with leading '0'.

	class Solution {
	public:
	bool helper(long long preNum, long long curNum, string numStr, int pos){
	if(pos==numStr.length())
	return true;
	string curNumStr = to_string(curNum);
	int len = curNumStr.length();
	if(len+pos-1>numStr.length()-1)
	return false;
	string _curNumStr = numStr.substr(pos, len);
	if(curNumStr!=_curNumStr)
	return false;
	long long nextNum = preNum + curNum;
	pos = pos+len;
	return helper(curNum, nextNum, numStr, pos);
	}
	bool isAdditiveNumber(string num) {
	if(num.length()<3)
	return false;
	for(int i=0; i<=num.size()/2 - 1; i++){
	if(num[0]=='0'&&i>0)
	return false;
	for(int j=i+1; j<=num.size()-2; j++){
	if(num[i+1]=='0'&&j>i+1)
	break;
	long long n0 = stod(num.substr(0, i+1));
	long long n1 = stod(num.substr(i+1, j-i));
	long long sum = n0+n1;
	bool res = helper(n1, sum, num, j+1);
	if(res)
	return true;
	}
	}
	return false;
	}
	};

view raw Q306.cpp hosted with ❤ by GitHub

Round 2 solution:

	bool helper(string num, vector<long>& nums, int idx){
	if(idx==num.size())
	return nums.size()>=3;
	if(nums.size()<2){
	for(int i=idx; i<idx+num.size()/2; i++){
	string str = num.substr(idx, i-idx+1);
	if(str[0]=='0'&&str.length()>1)
	continue;
	nums.push_back(stol(str));
	bool res=helper(num, nums, i+1);
	nums.pop_back();
	if(res==true)
	return true;
	}
	return false;
	}else{
	long cur = nums[nums.size()-1]+nums[nums.size()-2];
	string s = to_string(cur);
	if(idx+s.length()-1 >= num.length())
	return false;
	string curStr = num.substr(idx, s.length());
	if(curStr!=s||(curStr[0]=='0'&&curStr.length()>1))
	return false;
	nums.push_back(cur);
	bool res=helper(num, nums, idx+s.length());
	nums.pop_back();
	return res;
	}
	return true;
	}
	bool isAdditiveNumber(string num) {
	bool res=false;
	if(num.length()<=2)
	return res;
	vector<long> nums;
	res = helper(num, nums, 0);
	return res;
	}

view raw Q306Rnd2.cpp hosted with ❤ by GitHub