### 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"){
}
}

if (!pos){res="-"+res;}
return res;
}
};