Leetcode Additive Number problem solution

In this Leetcode Additive, Number problem solution Additive number is a string whose digits can form an 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. we have given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number.

Problem solution in Python.

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        
        def ableToSeeTheLight(n0, n1, num_str):
            s = str(n0+n1)
            #print("n0", n0, "n1", n1, "s", s, "num", num_str)
            if not num_str and num.endswith(str(n1)):
                return True
            
            if num_str.startswith(s):
                return ableToSeeTheLight(n1, int(s), num_str[len(s):])
            else:
                return False

        for i in range(1, len(num)):
            if i > 1 and num[0] == '0':
                continue
            for j in range(i + 1, len(num)):
                if j - i > 1 and num[i] == '0':
                    continue
                
                n0 = int(num[0:i])
                n1 = int(num[i:j])
                if ableToSeeTheLight(n0, n1, num[j:]):
                    return True
        return False

Problem solution in Java.

class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        if (n < 3) return false;
        for (int i = 1; i <= n / 2; i++) {
            if (i > 1 && num.charAt(0) == '0') break;
            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && num.charAt(i) == '0') break;
                long first = Long.parseLong(num.substring(0, i));
                long second = Long.parseLong(num.substring(i, j));
                int k = j;
                while (k < n) {
                    long target = first + second;
                    String s = String.valueOf(target);
                    if (k + s.length() <= n && num.substring(k, k + s.length()).equals(s)) {
                        k += s.length();
                        first = second;
                        second = target;
                    }
                    else break;
                }
                if (k == n) return true;
            }
        }
        return false;
    }
}

Problem solution in C++.

class Solution {
public:
    vector<long long> path;
    bool dfs(string& s, int start) {
        int sz = path.size();
        if (start == s.length() && path.size() >= 3) {
            return true;
        }
        long long n = 0, max_len;
        max_len = (s[start] == '0' ? 1 : 15); 
        for (int i = start; i < s.length() && max_len -- ; i++) {
            n = n * 10 + (s[i] - '0');
            if (sz >= 2 &&  path[sz - 1] + path[sz - 2] < n) return false;
            else if (sz <= 1|| path[sz - 1] + path[sz - 2] == n) {
                path.push_back(n);
                if (dfs(s, i + 1)) return true;
                path.pop_back();
            }
        }
        return false;
    }
    
    bool isAdditiveNumber(string& num) {
        return dfs(num, 0) ;
    }
};

Problem solution in C.

bool check(char* num, char* num1, char* num2, int last_idx){
    int num1_len = strlen(num1), num2_len = strlen(num2);
    if(num1_len>1 && num1[0] == '0' || num2_len>1 && num2[0] == '0' || last_idx > strlen(num)-1)
        return false;
    long long n1 = strtol(num1,NULL,10); 
    long long n2 = strtol(num2,NULL,10);
    long long sum = n1+n2;
    int sum_len = 0;
    while(sum>0){
        sum_len+=1;
        sum/=10;
    }
    if(last_idx+sum_len>strlen(num)-1)
        return false;
    char* sum1 = (char*)calloc(sum_len+1,sizeof(char));
    memcpy(sum1,num+last_idx+1,sizeof(char)*sum_len);
    sum1[sum_len] = '';
    sum = strtol(sum1,NULL,10);
    if(sum!=(n1+n2))
        return false;
    if(last_idx+sum_len == strlen(num)-1)
        return true;
    if(sum_len == 0)// for "000" test case
        sum_len = 1;
    return check(num,num2,sum1,last_idx+sum_len);
}

bool isAdditiveNumber(char * num){
    int len = strlen(num);
    for(int i=1;i<=len/2;i++){
        char* num1 = (char*)calloc(i+1,sizeof(char));
        memcpy(num1,num,sizeof(char)*i);
        num1[i] = '';
        for(int j=1;j<=(len-i)/2;j++){
            char* num2 = (char*)calloc(j+1,sizeof(char));
            memcpy(num2,num+i,sizeof(char)*j);
            num2[j] = '';
            if(check(num,num1,num2,i+j-1))
                return true;
        }
    }
    return false;
}

coding problems