Multiply Strings

String, Math

Medium

Given two non-negative integersnum1andnum2represented as strings, return the product ofnum1andnum2, 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 num1and num2is < 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