### Description

LeetCode 43

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"


Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

### Analysis

I think this problem is the base of implementing big integer class. The basic idea should be mastered.

Draw the graph of the multiplying process then we can obtain a conclusion, the length of result is at most the sum of the length of num1 and num2. And $$num1[i]*num2[j]$$ will be placed at indices $$[i+j, i+j+1]$$. Then just accumulate the elements placed every time. ### Solution

class Solution {
public String multiply(String num1, String num2) {
String r="";
int[] res=new int[num1.length()+num2.length()];
int s,mul;
for(int i=num1.length()-1;i>=0;i--)
{
for(int j=num2.length()-1;j>=0;j--)
{
s=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
s=s+res[i+j+1];
res[i+j]=res[i+j]+s/10;
res[i+j+1]=s%10;
}

}
for(int i=0;i<res.length;i++)
{
if(!(r.length()==0&&res[i]==0)) r=r+res[i];//Delete "0"s at high digits
}
if(r.length()==0) return "0";
else return r;
}
}


### Reference

 https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation