# 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[ ]`.

``````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

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

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

Code:

``````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