My solution with comments.


  • 0
    K

    The time complexity is o(nm) and the space used is o(n+m).
    A string res is used to record each digit of the multiplication.

     class Solution {
        public:
            string multiply(string num1, string num2) {
                if(num1.empty()||num2.empty()) return "";
                int n = num1.size(), m = num2.size();
                string res(n+m,'0'); //record each digit; the length of the multiplication of two numbers with size n and m is at most n+m.
                int i = n-1, j = m-1;
                int temp = 0, carry = 0;
                for(;i>=0;i--)
                {
                    j = m-1;
                    temp = 0; carry = 0;
                    for(;j>=0;j--)
                    {
                        temp = (num1[i]-'0')*(num2[j]-'0')+carry;
                        carry = temp/10;
                        temp %=10;
                        res[i+j+1]+=temp;
                        if(res[i+j+1]>='0'+10) {
                            carry += (res[i+j+1]-'0')/10;
                            res[i+j+1] =(res[i+j+1]-'0')%10+'0';
                        }
                    }
                    res[i+j+1] += carry;
                } 
                while(res[0]=='0'&&res.size()!=1) res=res.substr(1);  //remove the redundant ‘0’  
                if((num1[0]=='-'&&num2[0]!='-')||num1[0]!='-'&&num2[0]=='-') res.insert(res.begin(),'-');
                return res;
            }
        };

Log in to reply
 

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