Accepted 4ms c++ use vector


  • 0
    R

    private:

    const int _span = 9;
    const int _mask = 1000000000;
    vector<int> string2array( string str)
    {
        stringstream ss;
        vector<int> ret;
        for( int i = str.length(); i > 0;i -= _span )
        {
            int len = i < _span ? i : _span;
            ss.str( str.substr(i-len, len) );
            ss >> len;
            ss.clear();
            ret.push_back(len);
        }
        return ret;
    }
    
    string array2string( vector<int>& nums )
    {
        int i = 0;
        for (i = nums.size() - 1; i > 0; i --)
        {
            if(nums[i] > 0) break;
        }
        stringstream ss;
        for (; i >= 0; --i) {
            ss << nums[i];
            ss << setw(_span) << setfill('0');
        }
        return ss.str();
    }
    

    public:

    string multiply(string num1, string num2) {
        if( num1.empty() || num2.empty() ) return "";
        vector<int> num1_array = string2array(num1);
        vector<int> num2_array = string2array(num2);
        int len1 = num1_array.size();
        int len2 = num2_array.size();
        vector<int> result(len1+len2, 0);
        for( int i = 0; i < len1; ++i)
        {
            for(int j=0; j<len2; ++j)
            {
                long long tmp = (long long)num1_array[i] *  (long long)num2_array[j];
                tmp += (long long)result[i+j];
                //key point: num1_section_i  * num2_section_j only affect result_section_(i+j) 
                //You can easily catch it by assuming the section length is 1.
                result[i+j] = tmp % _mask; 
                result[i+j+1] += tmp / _mask;
            }
        }
        return array2string(result);
    }

Log in to reply
 

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