用字符串模拟乘法

题目链接-来源：力扣（LeetCode）

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

思路：

因为输入是字符串的形式，直观地思考可以采用模拟竖式的形式，对两个数分别从低位向高位按位作乘法，存储当前位的结果和进位结果进入一个结果数组。
考虑如下情形，我们计算 123 * 456，
index 0 1 2
num1 1 2 3
num2 4 5 6

    ...

(6* 2) 1 2
(5* 3) 1 5

当计算 123 * 456 的时候，我们要计算 123 * 6，123 * 5， 123 * 4，然后分别错位累加，需要多次考虑进位，保存中间结果。
我们可以对上述算法进行优化，简化我们的判断逻辑。
我们用一个 res[] 数组存储结果，易知 res[] 的长度最多为两乘数长度之和 len1 + len2，最少为 len1 + len2 - 1，res[0] 对应结果的最高位，res[len1 + len2 - 1] 对应最低位。对于上面的例子，考虑两个下标 i1 = 1，i2 = 2，我们发现结果的低位一定在 res[4]，也就是 res[i1 + i2 + 1]，高位一定在 res[i1 + i2]。
按照这个思路，我们每一次只需计算特定的 2 位，不需要额外保存中间结果。

注意边界条件，当 res[0] 为 0 时，我们可以从 res[1] 开始输出结果，除非结果本身为 0，这点我们可以单独考虑。

时间复杂度：O(mn)
空间复杂度：O(m + n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int len1 = num1.length(), len2 = num2.length();
        
        int[] res = new int[len1 + len2];
        
        for (int i = len1 - 1; i >= 0; i--) {
            int digit1 = num1.charAt(i) - '0';
            for (int j = len2 - 1; j >= 0; j--) {
                int digit2 = num2.charAt(j) - '0';
                int sum = res[i + j + 1] + digit1 * digit2;
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int start = res[0] == 0 ? 1 : 0;
        for (; start < res.length; start++) {
            sb.append(res[start]);
        }
        return sb.toString();
    }
}