C++ Simple Solution, Concise Code


  • 0
    class Solution {
        bool helper(string& num, int l1, int l2) {
            int n = num.size(), start = 0;
            while (start + l1 + l2 < n) {
                // num1 = num[start, start + l1), num2 = num[start + l1, start + l1 + l2)
                string res;
                bool f = false;
                for (int i = 0; i < max(l1, l2); i++) {
                    int val = (f ? 1 : 0) + (i >= l1 ? 0 : num[start + l1 - i - 1] - '0') + (i >= l2 ? 0 : num[start + l1 + l2 - i - 1] - '0');
                    res += val % 10 + '0';
                    f = val / 10;
                }
                if (f)
                    res += '1';
                reverse(res.begin(), res.end());
                // check
                for (int i = 0; i < res.size(); i++) {
                    if (start + l1 + l2 + i >= n || num[start + l1 + l2 + i] != res[i])
                        return false;
                }
                start += l1;
                l1 = l2;
                l2 = res.size();
            }
            return true;
        }
    public:
        bool isAdditiveNumber(string num) {
            int n = num.size();
            for (int i = 1; i + 1 < n; i++) {
                for (int j = 1; j <= i && j + i < n; j++) {
                    // check leading '0'
                    if ((i == 1 || num[j] != '0') && helper(num, j, i) || i != j && (j == 1 || num[i] != '0') && helper(num, i, j))
                        return true;
                }
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.