Sharing my 8ms C++ solution


  • 2
    T
    class Solution {
    public:
        string multiply(string num1, string num2) {
            // implementation of mannual multiplication
            // for arbitrarily large non-negative integers
            int n1 = num1.length();
            int n2 = num2.length();
            
            vector<int> DP(n1+n2, 0);
            int i, j;
            for(i=0; i<n1; i++)
                for(j=0; j<n2; j++)
                    DP[i+j+1] += (num1[i]-'0')*(num2[j]-'0');
                    
            string s;
            int temp;
            char tempchar;
            
            for(i=n1+n2-1; i>=0; i--)
            {
                if(i>0)
                    DP[i-1] += DP[i]/10;
                temp = DP[i]%10;
                tempchar = temp + '0';
                s = tempchar+s;
            }
        
            n1 = s.length();
            if(s[0] != '0')
                return s;
            else
            {
                int start=0;
                while(s[start] == '0')
                {
                    start = start+1;
                }
                if(s.length() > 0)
                    s =  s.substr(start, n1-start);
                if(s.length() == 0)
                    return "0";
                else
                    return s;
            }
        }
    };

Log in to reply
 

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