tech

Additive Number

Source

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.
More: leetcode

My Solution

给定一个字符串，该字符串只包含0~9的字符，判断该字符串会否为“可加”的。“可加”的定义如下：将字符串序列分解为整数（至少三个），除了前两个，其余的每个数都是它前两个数之和。
根据字符串的不同分解，可构造一棵解答树，再利用深度优先搜索寻找答案，注意处理以下几点。

  • ‘0x’是非法的；
  • 数的长度越长，值越大，利用此性质可以有效的剪枝；
  • 至少包含三个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        if(n < 3 )          // three numbers at least
            return false;
        for(int i = 1; i < n-1; i++)
        {
            if(num[0] == '0' && i > 1)   // "0x" is illegal
                break;
            for(int j = 1; i+j < n; j++)
            {
                if(num[i] == '0' && j > 1)
                    break;
                int first = str2int(num.substr(0, i));
                int second = str2int(num.substr(i, j));
                if(dfs(num, first, second, i+j))
                    return true;
            }
        }
        return false;
    }
private:
    // depth-first search
    bool dfs(string num, int first, int second, int idx)
    {
        if(first+second == str2int(num.substr(idx)))
            return true;
        for(int i = 1; i < num.size()-idx+1; i++)
        {
            if(num[idx] == '0' && i > 1)
                break;
            int third = str2int(num.substr(idx, i));
            if(first+second == third)
            {
                if(dfs(num, second, third, idx+i))
                    return true;
            }
            if(first+second < third) 
                break;
        }
        return false;
    }
    // string to int
    int str2int(string str)
    {
        int n = str.size();  
        if(n == 0 || (str[0] == '0' && n > 1) )
            return -1;
        int res = 0;
        for(int i = 0; i < str.size(); i++)
            res = res*10 + (str[i] - '0');
        return res;
    }
};