306. Additive Number - cocoder39/coco39_LC GitHub Wiki

306. Additive Number

corner case including leading '0', overflow. compare this problem with expression add op

pruning: i < num.size() / 2 and num.length() - j >= j - i

instead of generating substring from source and check if substring is equal to target, checking if target is prefix of source.

Bug report: use first instead of tmp in while loop will generate a bug. Because mismatch will break the while loop, updating second and third, but first won't be updated.

O(n ^ 3)

bool isAdditiveNumber(string num) {
        for (int i = 0; i < num.size() / 2; i++) {
            if (i != 0 && num[0] == '0')    return false;
            long long first = stol(num.substr(0, i + 1));
            
            for (int j = i + 1; num.length() - j >= j - i; j++) {
                if (j != i + 1 && num[i + 1] == '0')    break;
                long long second = stol(num.substr(i + 1, j - i));
                
                long long tmp = first;
                int start = j + 1;
                while (start < num.length()) {
                    string source = num.substr(start);
                    long long third = tmp + second;
                    string target = to_string(third);
                    if (source.length() < target.length() || source.substr(0, target.length()) != target)   break;
                    if (source.length() == target.length())    return true;
                    tmp = second;
                    second = third;
                    start += target.length();
                }
            }
        }
        return false;
    }