leetcode 306. Additive Number

亦凉 2022-08-20 12:19 151阅读 0赞

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.

// ConsoleApplication6.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<string>
    #include<vector>
    #include<iostream>
    #define MAX( x, y ) ( ((x) > (y)) ? (x) : (y) )
    using namespace std;
    class Solution {
    public:
    	bool check_once(vector<pair<string, pair<int, int> >>&nums)
    	{
    		bool flag = false;
    		vector<pair<string, pair<int, int> >>newnums;
    		for (int i = 0; i < nums.size(); i++)
    		{
    			if (nums[i].second.first == 0)
    			{
    				for (int len1 = 1; len1 <= nums[i].first.size() / 2; len1++)
    				{
    					for (int len2 = 1; len2 <= nums[i].first.size() / 2; len2++)
    					{
    						int len3 = MAX(len1, len2);
    						if (len1 + len2 + len3 <= nums[i].first.size())
    						{
    							if ((nums[i].first[0] == '0'&&len1>1) || (nums[i].first[len1] == '0'&&len2>1) ||
    								(nums[i].first[len1 + len2] == '0'&&len3>1))
    								continue;
    							else
    							{
    								int n1(0), n2(0), n3(0);
    								n1 = atoi((string(nums[i].first.begin(), nums[i].first.begin() + len1)).c_str());
    								n2 = atoi((string(nums[i].first.begin() + len1, nums[i].first.begin()
    									+ len1 + len2)).c_str());
    								n3 = atoi((string(nums[i].first.begin() + len1 + len2, nums[i].first.begin()
    									+ len1 + len2 + len3)).c_str());
    								if (n1 + n2 == n3)
    								{
    									if (len1 + len2 + len3 == nums[i].first.size())
    										return true;
    									else {
    										string str = nums[i].first;
    										str.erase(str.begin(), str.begin()
    											+ len1);
    										if (str.size() >= 3 && !(str.front() == '0'&&len2>1))
    											newnums.push_back(pair<string, pair<int, int> >(str,
    											pair<int, int>(len2, len3)));
    									}
    								}
    								else if (nums[i].first.size() > len1 + len2 + len3&& nums[i].first[len1 + len2] != '0')
    								{
    									n3 = atoi((string(nums[i].first.begin() + len1 + len2,
    										nums[i].first.begin() + len1 + len2 + len3 + 1)).c_str());
    									if (n1 + n2 == n3)
    									{
    										if (len1 + len2 + len3 + 1 == nums[i].first.size() )
    											return true;
    										else {
    											string str = nums[i].first;
    											str.erase(str.begin(), str.begin()
    												+ len1);
    											if (str.size() >= 3 && !(str.front() == '0'&&len2>1))
    												newnums.push_back(pair<string, pair<int, int> >(str, pair<int, int>(len2, len3 + 1)));
    										}
    									}
    								}
    							}
    						}
    					}
    				}
    			}
    			else
    			{
    				int len1 = nums[i].second.first;
    				int len2 = nums[i].second.second;
    				int n1(0), n2(0), n3(0);
    				n1 = atoi((string(nums[i].first.begin(), nums[i].first.begin() + len1)).c_str());
    				int len3 = MAX(len1, len2);
    				n2 = atoi((string(nums[i].first.begin() + len1, nums[i].first.begin() + len1 + len2)).c_str());
    				n3 = atoi((string(nums[i].first.begin() + len1 + len2, nums[i].first.begin() + len1 + len2 + len3)).c_str());
    				if (n1 + n2 == n3)
    				{
    					if (len1 + len2 + len3 == nums[i].first.size())
    						return true;
    					else{
    						string str = nums[i].first;
    						str.erase(str.begin(),str.begin() + len1);
    						if (str.size() >= 3 && !(str.front() == '0'&&len2>1))
    							newnums.push_back(pair<string, pair<int, int> >(str, pair<int, int>(len2, len3)));
    					}
    				}
    				else if (nums[i].first.size() > len1 + len2 + len3&& nums[i].first[len1 + len2] != '0')
    				{
    					n3 = atoi((string(nums[i].first.begin() + len1 + len2,
    						nums[i].first.begin() + len1 + len2 + len3 + 1)).c_str());
    					if (n1 + n2 == n3)
    					{
    						if (len1 + len2 + len3 + 1 == nums[i].first.size())
    							return true;
    						else {
    							string str = nums[i].first;
    							str.erase(str.begin(),str.begin() + len1);
    							if (str.size() >= 3 && !(str.front() == '0'&&len2>1))
    								newnums.push_back(pair<string, pair<int, int> >(str, pair<int, int>(len2, len3 + 1)));
    						}
    					}
    				}
    			}
    		}
    		nums = newnums;
    		return false;
    	}
    	bool isAdditiveNumber(string num)
    	{
    		bool f = false;
    		vector<pair<string, pair<int, int> >>nums;
    		nums.push_back(pair<string, pair<int, int> >(num, pair<int, int>(0, 0)));
    		while (nums.size() >= 1 && !f)
    		{
    			f = check_once(nums);
    		}
    		return f;
    	}
    };
    int _tmain(int argc, _TCHAR* argv[])
    {
    	string num = "12122436";
    	Solution sl;
    	cout << sl.isAdditiveNumber(num);
    	system("pause");
    	return 0;
    }

acceped！