Additive Number

2016-04-19

问题描述

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.

思路

本题可以使用DFS搜索，按顺序遍历每种情况，遇到满足的条件直接返回TRUE。

DFS的状态转移很关键：

//add1: 第一个数的长度
//add2: 第二个数的长度
//s:    剩余字符
bool DFS(int add1, int add2, string s);
//判断s1 + s2 是否数学上等于s3从左向右依次增大的子串
//大于或**小于整个s3**返回0，
//等于则返回s3子串的位置，递归调用DFS。
int canSum(string s1, string s2, string s3);

canSum函数做了剪枝，DFS不需要遍历所有情况，大大减少时间复杂度。

Code

具体代码如下：


class Solution {
public:
    bool isAdditiveNumber(string num) {
        if(num.size() < 3) return false;
        return dfs(0, 0, num);
    }
    bool dfs(int l1, int l2, string s) {
        int idx = canSum(s.substr(0, l1), s.substr(l1, l2), s.substr(l1 + l2));
        if(idx && l1 + l2 + idx == s.size()) {
            return true;
        }
        else if(idx) {
            if(canSum(s.substr(l1).substr(0, l2), s.substr(l1).substr(l2, idx), s.substr(l1).substr(l2 + idx)) && dfs(l2, idx, s.substr(l1)))
                return true;
        }
        else {
            for(int i = l1 ; i < s.size(); i++)
                for(int j = l2; j + i < s.size(); j++)
                    if(i != l1 || j != l2) {
                        if(canSum(s.substr(0, i), s.substr(i, j), s.substr(i + j)) && dfs(i, j, s))
                            return true;
                    }
        }
        return false;
    }
    int canSum(string s1, string s2, string s3) {
        if(s1 == "" || s2 == "" || s3 == "") return 0;
        else if(s1[0] == '0' && s1.size() > 1 || s2[0] == '0' && s2.size() > 1 || s3[0] == '0' && s3.size() > 1) return 0;
        for(int i = max(s1.size(), s2.size()) - 1; i < s3.size(); i++) {
            int tmp = judge(s1, s2, s3.substr(0, i + 1));
            if(tmp == 1)
                return i + 1;
            else if(tmp == 2)
                return 0;
        }
        return 0;
    }
    
    int judge(string s1, string s2, string s3) {
        stringstream ss1(s1), ss2(s2), ss3(s3);
        long long n1, n2, n3;
        ss1 >> n1; ss2 >> n2; ss3 >> n3;
        if(n1 + n2 == n3) return 1;
        else if(n1 + n2 < n3) return 2;
        else return 0;
    }
};