C++ implementation 23333333333


  • 0
    2

    Thanks to the post from @zjh08177

    The solution is not difficult to come up with, but I do think the solution is not elegant enough.....

    Here I just post the formated C++ implementation .....

    I hope you can offer me a more elegant solution ..... Thanks a lot ...

    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            for(int i = 1; i <= num.size()/2; i++) {
                for(int j = 1; j <= (num.size() - i)/2; j++) {
                    if(check_sum(num.substr(0, i), num.substr(i, j), num.substr(i + j)))  
                        return true;
                }
            }
            return false;
        }
        
        bool check_sum(string num1, string num2, string num) {
            if((num1.size() > 1 && num1[0] == '0') || (num2.size() > 1 && num2[0] == '0'))
                return false;
            string sum = add_string(num1, num2);
            if(sum == num) return true;
            if(num.size() <= sum.size() || sum.compare(num.substr(0, sum.size())) != 0)  return false;
            else return check_sum(num2, sum, num.substr(sum.size()));
        }
        
        string add_string(string m, string n) {
            string result;
            int i = m.size()-1, j = n.size()-1, carry = 0;
            while(i >= 0 || j >= 0) {
                int sum = carry + (i>=0 ? m[i--]-'0': 0) + (j>=0 ? n[j--]-'0': 0);
                result.push_back(sum % 10 + '0');
                carry = sum / 10;
            }
            if(carry)  result.push_back(carry + '0');
            reverse(result.begin(), result.end());
            return result;
        }
    };

  • 0
    2

    I have marked all the bugs I made ....... 233333333333

    I should be more serious to solve this problem next, it is composed of some different ideas

    class Solution {
    public:
        bool isAdditiveNumber(string num) {
            int size_num = num.size();
            for(int i = 1; i <= (size_num / 2); i++){
                for(int j = 1;  j <= (size_num - i)/2; j++) {
                    string num1 = num.substr(0, i);
                    string num2 = num.substr(i, j);
                    string num3 = num.substr(i + j);
                    if(check2sum(num1, num2, num3))
                        return true;
                }
            }
            return false;
        }
        
        
        bool check2sum(string num1, string num2, string num3) {
            /*** bugs **/
            if(valid_str(num1) || valid_str(num2) || valid_str(num3))  return false;
            string sum = add_str(num1, num2);
            //cout<<num1<<"+"<<num2<<"="<<sum<<endl;
            /** bugs **/
            if(sum == num3)  return true;
            if(sum.size() > num3.size())  return false;
            if(sum == num3.substr(0, sum.size()))
                return check2sum(num2, sum, num3.substr(sum.size()));
            else 
                return false;
        }
        
        string add_str(string s1, string s2) {
            int size1 = s1.size(), size2 = s2.size();
            if(size1 == 0)  return s2;
            if(size2 == 0)  return s1;
            
            string result;
            int carry = 0;
            for(int end1 = size1 - 1, end2 = size2 - 1;  end1 >= 0 || end2 >= 0; end1--, end2--) {
                int temp = carry + (end1 >= 0 ? s1[end1]-'0' : 0) + (end2 >= 0 ? s2[end2]-'0' : 0);
                result += to_string(temp % 10);
                carry = temp / 10;
            }
            /** bugs **/
            if(carry)  result += to_string(carry);
            reverse(result.begin(), result.end());
            return result;
        }
        
        bool valid_str(string s) {
            return s.size() > 1 && s[0] == '0';
        }
    };

Log in to reply
 

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