# Multiply Strings

`String`, `Math`

**Medium**

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 & Solution

### 九章的解法要点：

* 两个位数为 `m` 和 `n` 的数字相乘，乘积不会超过 `m + n` 位。
* 乘法操作从右往左计算时，每次完成相加就确定了当前 digit. 并且是在`res[i + j + 1]`位上，需要跟当前值，进位值共同确定最终保留的digit。
* 同一个 digit 多次修改，用 `int[ ]`.

```java
public class Solution {
    public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null) return null;

        int maxLength = num1.length() + num2.length();
        int[] nums = new int[maxLength];
        int i, j, product, carry;

        for(i = num1.length() - 1; i >= 0; i--){
            // 中间部分相当于多位数乘一位数，起始 carry 为 0
            carry = 0;
            for(j = num2.length() - 1; j >= 0; j--){
                int a = num1.charAt(i) - '0';
                int b = num2.charAt(j) - '0';

                product = nums[i + j + 1] + a * b + carry;
                nums[i + j + 1] = product % 10;
                carry = product / 10;
            }
            // 循环结束，最左面为当前最高位数，如果 carry 还有就设过去
            nums[i + j + 1] = carry;
        }
        StringBuilder sb = new StringBuilder();
        int index = 0;
        while(index < maxLength - 1 && nums[index] == 0) index ++;
        while(index < maxLength) sb.append(nums[index++]);

        return sb.toString();
    }
}
```

### 更优雅的方法 by [yavinci](https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation)：

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

基于了一个乘法特性：每个数字相乘时：

```java
 num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]

 [i + j] 是进位
 [i + j + 1] 是当前位
```

Code:

```java
public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] pos = new int[m + n];

    for(int i = m - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];

            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  

    StringBuilder sb = new StringBuilder();
    for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
    return sb.length() == 0 ? "0" : sb.toString();
}
```

## Reference

<https://mnmunknown.gitbooks.io/algorithm-notes/525_string_za_ti.html>

<https://leetcode.com/problems/multiply-strings/discuss/17608/AC-solution-in-Java-with-explanation>