Multiply Two 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.

Discussion: This problem is just like how to multiply two large numbers (the scales of which are larger than integers). We use the rule of multiplication's we have learned in elementary school to solve it.

Two important things to notice:
1. Do not forget the carrier at the beginning.
2. Do not add the beginning "0"s to the result.

Java: Multiply Strings

01 public String multiply(String num1, String num2) {      
02   char[] n1=num1.toCharArray();
03   char[] n2=num2.toCharArray();
04   int m=n1.length;
05   int n=n2.length;
06   int[] result=new int[m+n];
07   for(int i=0;i<result.length;i++)
08     result[i]=0;
09 
10   int j=n-1;
11   int shift=0;
12   while(j>=0)
13   {
14     int carrier=0;
15     int multiplier=n2[j]-'0';
16     int multiplicant=0;
17     int value=0;
18     int k=shift;
19     for(int i=m-1;i>=0;i--)
20     {
21       multiplicant=n1[i]-'0';
22       int sum=carrier+multiplier*multiplicant+result[k];
23       value=sum%10;              
24       result[k]=value;              
25       carrier=sum/10;
26       k++;
27     }
28     if(carrier>0)
29       result[k]=carrier;
30     shift++;
31     j--;
32   }
33 
34   StringBuffer sb=new StringBuffer();      
35   int end=result.length-1;
36   if(end==0)
37     sb.append(result[end]);      
38   while(result[end]==0 && end>0)
39     end--;
40   for(int i=end;i>=0;i--)
41   {          
42     sb.append(result[i]);
43   }
44   return sb.toString();
45 }