# 43. Multiply Strings

[Link](https://leetcode.com/problems/multiply-strings/)

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.

**Solution**

n1位數跟n2位數的乘機最多就是n1+n2位數。\
999 \* 999 <= 999 \* 1000 <= 999000 , 3位數乘3位數最多六位數

概念是用把每個位數乘法的值先存到array\[n1+n2+1]中，然後之後處理溢位問題。\
其中n1是a.length(), n2是b.length()，\\

```
public String multiply(String num1, String num2) {
        int n1 = num1.length(), n2 = num2.length();
        int[] product = new int[n1+n2];
        for(int i = n1-1; i >= 0; i--){
            for(int j = n2-1; j >= 0; j--){
                
                product[i+j+1] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                
            }
        }
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = n1+n2-1; i >= 0; i--){
            int sum = product[i] + carry;
            sb.append(sum%10);
            carry = sum/10;
        }
        if(carry != 0){
            sb.append(carry);
        }
        
        //特別處理是0開頭的結果。
        while(sb.length() != 0 && sb.charAt(sb.length()-1) == '0' )
        {
            sb.deleteCharAt(sb.length()-1);
        }
        
        return sb.length() == 0? "0": sb.reverse().toString();
        
    }
```
