leetcode Question 58: Multiply Strings

Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Analysis:

Straight forward idea. Just like the way we multiply numbers. Don't forget considering the carry and be careful. e.g.

  123*456,

what we usually do is:


      123
*    456
-----------

      738
    615
+492
-----------
  56088
thus, 123*456 = 56088.

In the same way, the algorithm is:
A*B
(1)For each element B[i]
    Compute tmp = B[i]*A
    Add tmp to the previous result, note the start position. res = res"+"tmp
(2)Return result.

To be specific,
(1) char2int,     int(char-'0');
(2) int2char,     char(int+'0')
(3) Don't forget the carry in each add or multiply operation.
(4) Don't forget the carry after last operation. e.g.  82+33 = 115.
(5) Be careful with the string order and the number order.

Update (201309) Code:

class Solution {
public:

    string mpl(string num, char n){  //compute num*n
        string res="";
        int carry=0;    
        if (n=='0'){return "0";}
        for (int i=num.size()-1;i>=0;i--){
            int m=(num[i]-'0')*(n-'0')+carry;
            carry = m/10;
            m=m%10;
            res = char(m+'0')+res;
        }
        if (carry!=0){res = char(carry+'0')+res;}
        return res;
    }

    void add(string &res, string m,int idx){
        if (res==""){ res = m;}
        else{
            m = m+string(idx,'0'); // this is important (you can also change value i instead)
            int carry=0;
            int i=res.size()-1;
            int j=m.size()-1;
            while (i>=0){
                int k =(res[i]-'0')+(m[j]-'0')+carry;
                carry=k/10;
                k=k%10;
                res[i]=char(k+'0');
                i--; j--;
            }
            while (j>=0){ // deal with the rest of string
                if (carry>0){
                    int kk = (m[j]-'0')+carry;
                    carry = kk/10;
                    kk=kk%10;
                    res= char(kk+'0')+res;
                }else{
                    res = m[j]+res;
                }
                j--;
            }
            
            if (carry>0){ // be careful with highest digit
                res = char(carry+'0')+res;
            }
        }
    }

    string multiply(string num1, string num2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function                
        if (num1.size()==0 || num2.size()==0){return "";}
        //handle negative case
        bool pos=true; 
        if (num1[0]=='-'){num1=num1.substr(1);pos = !pos;}
        if (num2[0]=='-'){num2=num2.substr(1);pos = !pos;}

        //main part
        string res="0";        
        for (int i=num2.size()-1;i>=0;i--){ //for each element in num2        
            string m=mpl(num1,num2[i]); // num1 multiply by num2[i]           
            if (m!="0"){
                add(res,m,num2.size()-1-i); // add m to the result
            }
        }
                
        if (!pos){res="-"+res;}
        return res;
    }
};