题目描述

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

样例

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

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

说明：

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

算法分析

模拟

• 1、长度是n和长度是m的数字相乘，最多只有n + m位，为了方便计算，将num1和num2反向存储到a[]和b[]中，即位数低的在前面，且开一个大小是n + m的c[]存储计算后的答案
• 2、两个数相乘时，将a[i] * b[j]的结果累加到c[i + j]中，最后c[i + j]表示i + j这个位数的值是c[i + j]
• 3、由于某些位的数字有可能是大于等于10的，因此从0枚举到n + m - 1，借助t，将所有位的值全部变成个位数
• 4、找到相乘后的数字的数组末端k，越靠后位数越高，将[0,k]的元素进行反转输出

时间复杂度 $O(nm)$

Java 代码

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0")||num2.equals("0"))
           return "0";
        int n = num1.length();
        int m = num2.length();
        int[] a = new int[n];
        int[] b = new int[m];
        for(int i = 0;i < n;i ++) a[i] = num1.charAt(n - i - 1) - '0';
        for(int i = 0;i < m;i ++) b[i] = num2.charAt(m - i - 1) - '0';

        int[] c = new int[n + m];
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < m;j ++)
                c[i + j] += a[i] * b[j];

        int t = 0;

        for(int i = 0;i < n + m;i ++)
        {
            t += c[i];
            c[i] = t % 10;
            t /= 10;
        }
        int k = n + m - 1;
        while(k >= 0 && c[k] == 0) k --;
        StringBuilder sb = new StringBuilder("");
        for(int i = k;i >= 0;i --)
            sb.append(c[i]);
        return sb.toString();
    }
}