Neat recursive c++ code in 0ms with comments


  • 0
    A
    1. generate one number each recursion, push one digit to the number each for loop
    2. using long long to handle large number
    3. num[index] == '0' && i != index means this is a invalid number with leading zero
    
    class Solution {
        bool res = false;
    public:
        bool isAdditiveNumber(string num) {
            helper(num, 0, 0);
            return res;
        }
        void helper(string& num, int index, long long prev){
            long long curr = 0;
            for(int i = index; i < num.size(); i++){
                if(num[index] == '0' && i != index) return;// get rid of leading zero case
                curr = curr*10 + (num[i] - '0'); // push one digit each time
                if(index == 0)  helper(num, i+1, curr);// continue looking for the next number
                else{// start to check the additive sequence
                    string ans = to_string(prev + curr);
                    if(i + ans.size() < num.size() && ans == num.substr(i+1, ans.size())){
                        if(i + ans.size() == num.size()-1){ res = true; return;}
                        helper(num, i+1, curr);
                    }else continue;// sequence not satisfied, push one more digit in next loop
                }
                if(res) return;// just return when valid sequence is found
            }
        }
    };

Log in to reply
 

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