Share my C++ solution,easy to understand


  • 0
    V
    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            int n = num.length();
            long long int num1 = 0;
            long long int num2 = 0;
            long long int num3 = 0;
            
            for (int i = 1; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    string s1 = num.substr(0, i);
                    string s2 = num.substr(i, j - i);
                    string add_num = s1 + s2;
                    
                    if ((s2.size() > 1 && s2[0] == '0') || (s1.size() > 1 && s1[0] == '0'))
                        continue;
                    
                    num1 = atoll(s1.c_str());
                    num2 = atoll(s2.c_str());
                    num3 = num1 + num2;
                    string s3 = to_string(num3);
                    
                    if (num.find(s3, add_num.length()) != add_num.length())
                        continue;
                    
                    add_num += s3;
                    while (add_num.size() < n)
                    {
                        num1 = num2;
                        num2 = num3;
                        num3 = num1 + num2;
                        s3 = to_string(num3);
                        
                        if (num.find(s3, add_num.length()) != add_num.length())
                            break;
                        
                        add_num += s3; 
                    }
                    
                    if (add_num.compare(num) == 0)
                        return true;
                }
            }
            
            return false;
        }
    };

Log in to reply
 

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