题目描述

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

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

1. num1 和 num2 的长度小于110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

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

解法1

首先, 我们观察示例2中123*456的竖式计算过程, 用乘数456的每一位与被乘数123相乘, 得到的乘积依次向左“移位”、相加. 123*6的乘积为738, 向左移动0位. 123*5的乘积为615, 向左移动1位. 123*4的乘积位492, 向左移动2位. 然后我们将这三个被向左移动了0位、1位、2位的数相加, 就模拟了乘法的过程.观察123*456竖式

        1 2 3

   x   4 5 6

————————-

        7 3 8

     6 1 5

  4 9 2

————————-

  5 6 0 8 8

经过上面的分析, 我们需要完成两个函数, 第一个函数实现了被乘数与乘数的每一位相乘. 第二个函数实现了乘法结果相加. 我们首先实现第一个乘法函数 – numMultiCh.

private String numMultiCh(String num, char c) {
        char[] res = new char[num.length() + 1];
        int carry = 0;

        for (int i = num.length() - 1; i >= 0; i--) {
            int t = (num.charAt(i) - '0') * (c - '0') + carry;

            res[i + 1] = (char) ('0' + t % 10);
            carry = t / 10; // 记录本次乘法的进位结果, 共下一次乘法使用
        }

        res[0] = (char) ('0' + carry);
        return new String(res);
}

上面的函数逆序遍历被乘数的每一位, 与数字c相乘. 如果乘积大于10, 那么carry会记录进位的结果. 当遍历到被乘数的下一位时, 我们将上次产生的进位累计起来.

接下来我们实现两个用字符串表示的数字的加法, numAdd方法实现了该过程. 为了便于实现, 若遇到两个数字的长度不等, 例如738 + 6150. 我们会对较短的数字补上前导符0. 这样, 两个数字将会变成0738+6150. 我们只需要将对应位相加, 并做一些进位处理即可. 还有一点需要考虑, 长度m的数与长度n的数相加, 结果最多是多少位? 多举几个例子, 就很容易的算出结果最多为max(m, n) + 1. 例如99+1=100. 如果我们能计算出相加后的结果, 可以存储字符串空间的重新分配, 来提高字符串处理的效率.

public String numAdd(String num1, String num2) {
        // 补上前导符0, 便于对应位相加
        if (num1.length() > num2.length()) {
            for (int i = 0; i < num1.length() - num2.length(); i++)
                num2 = '0' + num2;
        } else if (num1.length() < num2.length()) {
            for (int i = 0; i < num2.length() - num1.length(); i++)
                num1 = '0' + num1;
        }
        // 存储相加后的结果
        char[] res = new char[num1.length() + 1];
        int carry = 0;

        for (int i = num2.length() - 1; i >= 0; i--) {
            int t = (num1.charAt(i) - '0') + (num2.charAt(i) - '0') + carry;
            res[i + 1] = (char) ('0' + t % 10);
            carry = t / 10; // 处理进位
        }
        // 当最低位相加后, 可能产生进位
        res[0] = (char) ('0' + carry);
        return new String(res);
}

最后, 我们实现函数multiply完成整个字符串相乘的过程. 我们首先取被乘数与乘数的最高位, 将相乘的结果保存到tmp中(竖式结果的第一行). 然后遍历乘数的次高位, 将相乘的结果(竖式结果的第二行)末尾补上一个0, 与tmp相加. 循环此过程, 直到乘数被遍历完毕.

class Solution {
    private String numMultiCh(String num, char c) {
        char[] res = new char[num.length() + 1];
        int carry = 0;

        for (int i = num.length() - 1; i >= 0; i--) {
            int t = (num.charAt(i) - '0') * (c - '0') + carry;

            res[i + 1] = (char) ('0' + t % 10);
            carry = t / 10;
        }

        res[0] = (char) ('0' + carry);
        return new String(res);
    }

    public String numAdd(String num1, String num2) {

        if (num1.length() > num2.length()) {
            for (int i = 0; i < num1.length() - num2.length(); i++)
                num2 = '0' + num2;
        } else if (num1.length() < num2.length()) {
            for (int i = 0; i < num2.length() - num1.length(); i++)
                num1 = '0' + num1;
        }

        char[] res = new char[num1.length() + 1];
        int carry = 0;

        for (int i = num2.length() - 1; i >= 0; i--) {
            int t = (num1.charAt(i) - '0') + (num2.charAt(i) - '0') + carry;
            res[i + 1] = (char) ('0' + t % 10);
            carry = t / 10;
        }

        res[0] = (char) ('0' + carry);
        return new String(res);
    }

    public String multiply(String num1, String num2) {
        String tmp = numMultiCh(num1, num2.charAt(num2.length() - 1));
        String suff = "0";

        for (int j = num2.length() - 2; j >= 0; j--) {
            String tmp1 = numMultiCh(num1, num2.charAt(j)) + suff;

            tmp = numAdd(tmp, tmp1);
            suff += '0';

        }

        int idx;
        for (idx = 0; idx < tmp.length(); idx++) {
            if (tmp.charAt(idx) != '0')
                break;
        }


        if (idx == tmp.length())
            return "0";
        return tmp.substring(idx);
    }
}

解法2(对上述过程的简化)

如果我们熟悉了上述乘法竖式计算的过程, 我们可以对代码简化. 我们编写双重循环, 外层循环逆序遍历被乘数的每一位, 内层循环逆序遍历乘数的每一位. 将对应的数字直接相乘. 如果乘积大于10, 就取余作为本位的结果, 将进位记录下来供下一次乘法使用.

有一点需要考虑清楚, 对应位相乘的结果应该保存到乘积结果的哪一位呢? 我们先要知道两个数相乘, 最多能产生几位的乘积. 多举几个例子, 100*100 = 10000, 99*99 = 9801, 1000*1=1000. 第一个例子由两个三位数产生出了5位数, 第二个例子由两个2位数产生了4位数. 第三个例子由4位数和1位数产生了4位数. 很容易的可以看出, m位数与n位数相乘最多能产生m+n位的乘积.

我们知道了乘积的位数, 就可以计算索引向乘积数组里填充了. 我们将乘积记为result, 乘数记为num1, 被乘数记为num2. 我们还是用123*456这个例子计算索引, 双重循环逆序遍历123与456, 外层计数器变量记为i, 内侧计数器变量记为j. 当取被乘数123中的数字3, 取乘数456中的数字6时, i和j都为2. 而乘积的长度为6. 3与6相乘的结果一定是乘积的最后一位, 最后一位的索引是5. 那么我们可以计算出乘积result[i+j+1] = num1[i]*num[j] % 10 + carry. 需要注意的是, 我们还需要考虑进位情况, 我们使用carry变量表示是否产生进位, carry=num[i]*num[j] / 10, carry变量初始值为0.

综上, 我们可以根据解法1的代码优化, 得到解法2的代码.

class Solution {
    public String multiply(String num1, String num2) {
        int[] res = new int[num1.length() + num2.length()];
        for (int i = num2.length() - 1; i >= 0; i--) {
            int carry = 0;

            for (int j = num1.length() - 1; j >= 0; j--) {
                res[i + j + 1] += (num2.charAt(i) - '0') * (num1.charAt(j) - '0') + carry;
                carry = 0; // carry用完一定要清空

                if (res[i + j + 1] > 9) {
                    carry = res[i + j + 1] / 10;
                    res[i + j + 1] %= 10;
                }
            }
            res[i] = carry; // case：上面当for循环结束后，可能会进位，所以要记录进位
        }

        StringBuilder s = new StringBuilder();
        boolean start = false;

        // 跳过0前导符
        for (int i : res) {
            if (i != 0)
                start = true;
            if (start)
                s.append(i);
        }

        return s.length() == 0 ? "0" : s.toString();
    }
}