题目描述

题目链接

https://leetcode.cn/problems/multiply-strings/

思路

1. 做加法

如果和之一是，则直接将作为结果返回即可。如果和都不是，则可以通过模拟「竖式乘法」的方法计算乘积，竖式乘法就是我们平常学习生活中常用的对两个整数相乘的方法，即从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。

这道题中，被乘数是，乘数是。注意，除了最低位以外，其余的每一位的运算结果都需要在低位补。

我们对每次得到的结果进行累加，可以使用「竖式加法」的方法。竖式加法就是模拟对两个整数相加的操作，思路如下图所示：首先将相同数位对齐，从低到高逐位相加，如果当前位和超过，则向高位进一位。

具体来说，我们定义两个指针和分别指向和的末尾，即最低位，同时定义一个变量维护当前是否有进位，然后从右向左逐位相加即可。如果两个数字的位数不同，我们统一在指针当前下标处于负数的时候返回，等价于对位数较短的数字进行了补零操作，这样就可以解决两个数字位数不同的情况。

具体代码实现如下：

public String multiply(String num1, String num2) {
    if (num1.equals("0") || num2.equals("0")) {
        return "0";
    }
    String ans = "0";
    int m = num1.length(), n = num2.length();
    // 乘数从右向左遍历
    for (int i = n - 1; i >= 0; i--) {
        StringBuilder curr = new StringBuilder();
        // 是否进位
        int add = 0;
        // 低位补0
        for (int j = n - 1; j > i; j--) {
            curr.append(0);
        }
        int y = num2.charAt(i) - '0';
        for (int j = m - 1; j >= 0; j--) {
            int x = num1.charAt(j) - '0';
            int product = x * y + add;
            curr.append(product % 10);
            add = product / 10;
        }
        if (add != 0) {
            curr.append(add % 10);
        }
        ans = addStrings(ans, curr.reverse().toString());
    }
    return ans;
}
public String addStrings(String num1, String num2) {
    int i = num1.length() - 1, j = num2.length() - 1, add = 0;
    StringBuilder ans = new StringBuilder();
    while (i >= 0 || j >= 0 || add != 0) {
        int x = i < 0 ? 0 : num1.charAt(i--) - '0';
        int y = j < 0 ? 0 : num2.charAt(j--) - '0';
        int sum = add + x + y;
        ans.append(sum % 10);
        add = sum / 10;
    }
    return ans.reverse().toString();
}

• 时间复杂度：，其中和分别是和的长度。需要从右往左遍历，对于的每一位，都需要和的每一位计算乘积，因此计算乘积的总次数是。字符串相加操作共次，相加的字符串长度最长为，字符串相加的时间复杂度是。总时间复杂度是，即。
• 空间复杂度：，其中和分别是和的长度。空间复杂度取决于存储中间状态的字符串，由于乘积的最大长度为，因此存储中间状态的字符串长度不会超过。

  2. 做乘法

  方法一中的做法是从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，整个过程中涉及到较多字符串相加的操作。如果使用数组代替字符串存储结果，则可以减少对字符串的操作。

我们令和分别表示和的长度，并且它们均不为，则和的乘积的长度肯定为或。证明如下：

• 如果和都取最小值（100…），则、，相乘可得，此时乘积的长度为；

• 如果和都取最大值（999…），则、，相乘可得，乘积显然小于且大于，因此乘积的长度为。

由于和的乘积的最大长度为，因此创建长度为的数组用于存储乘积结果。对于任意和，的结果位于，如果，则将进位部分加到。最后，将数组转成字符串，如果最高位是则舍弃最高位。 具体代码实现如下：

public String multiply(String num1, String num2) {
    if ("0".equals(num1) || "0".equals(num2)) {
        return "0";
    }
    int m = num1.length(), n = num2.length();
    int[] ansArr =  new int[m + n];
    // 从低位到高位遍历num1，对于num1中的每个位，分别与num2中的每个位相乘
    for (int i = m - 1; i >= 0; i--) {
        int x = num1.charAt(i) - '0';
        for (int j = n - 1; j >= 0; j--) {
            int y = num2.charAt(j) - '0';
            ansArr[i + j + 1] += x * y;
        }
    }
    // 从后往前解决进位问题
    for (int i = m + n - 1; i > 0; i--) {
        if (ansArr[i] >= 10) {
            ansArr[i -1] += ansArr[i] / 10;
            ansArr[i] = ansArr[i] % 10;
        }
    }
    // 组装结果
    StringBuilder ans = new StringBuilder();
    int start = ansArr[0] == 0 ? 1 : 0;
    for (int i = start; i < ansArr.length; i++) {
        ans.append(ansArr[i]);
    }
    return ans.toString();
}

• 时间复杂度：，其中和分别是和的长度。需要计算的每一位和的每一位的乘积。
• 空间复杂度：，其中和分别是和的长度。需要创建一个长度为的数组存储乘积。