- 题目描述

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

说明：

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

来源：LeetCode

- 示例

• 示例 1:
  输入: num1 = “2”, num2 = “3”
  输出: “6”
• 示例 2:
  输入: num1 = “123”, num2 = “456”
  输出: “56088”

- 思路分析

我用示例2来说。首先生成一个全为 0 0 0的数组 s u m = [ 0 , 0 , 0 ] sum = [0, 0, 0] sum=[0,0,0]和结果字符串 a n s = " " ans = "" ans=""。从 n u m 2 num2 num2的尾巴开始：

1. 将 n u m 2 num2 num2逐位和 n u m 1 num1 num1相乘，然后将每一位的结果保存在一个长度等于 n u m 1 num1 num1长度的数组里。即：先用 n u m 2 num2 num2的 6 6 6分别和 n u m 1 num1 num1的 “ 3 ” “3” “3”， “ 2 “ “2“ “2“， ” 1 “ ”1“ ”1“相乘，得到三个数 18 18 18， 12 12 12， 6 6 6，将这三个数保存在数组 t e m p temp temp里，得到 t e m p = [ 18 , 12 , 6 ] temp = [18, 12, 6] temp=[18,12,6]。
2. 将 s u m sum sum的每一位和 t e m p temp temp的对应位置相加得到新的 s u m sum sum。即 s u m = [ 18 , 12 , 6 ] sum = [18, 12, 6] sum=[18,12,6]。
3. 将新 s u m sum sum第一位的个位数加入结果字符串，将十位上的数字加到 s u m [ 1 ] sum[1] sum[1]。即 s u m = [ 18 , 13 , 6 ] sum = [18, 13, 6] sum=[18,13,6], a n s = " 8 " ans = "8" ans="8"。
4. 除了第一位以外，将 s u m sum sum全部前移一位，然后最后一位改为 0 0 0。即 s u m = [ 13 , 6 , 0 ] sum = [13, 6, 0] sum=[13,6,0]。
   当乘积结果位数大于 n u m 1 num1 num1的长度时，需要对 s u m sum sum还没有加入结果字符串的部分进行处理。即从 s u m sum sum第一位开始，将该数的个位数加入字符串，十位数加到 s u m sum sum的下一位。然后再去除字符串前面可能的 0 0 0即可。

- JAVA实现

class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length(), len2 = num2. length();
        if(len1==0 || len2==0) return "0";
        String ans = "";
        int[] sum = new int[len1];
        for(int m=0;m<len1;m++) sum[m] = 0;  //初始化
        int[] temp = new int[len1];
        for(int j=len2-1;j>=0;j--) {
            for(int i=len1-1;i>=0;i--) {
                int multi = (num1.charAt(i) - 48) * (num2.charAt(j) - 48);
                temp[len1-1-i] = multi;   //低位乘积保存在数组前面
            }
            int units = (temp[0] + sum[0]) % 10;   //得到个位数
            int tens = (temp[0] + sum[0]) / 10;    //得到十位数
            ans = units + ans; 
            //如果num1的长度为1，乘积可能是一位数也可能是两位数
            //乘积是两位数的情况在这里特殊处理
            if(len1 == 1 && tens > 0) sum[0] = tens;
            else sum[0] = 0;
            //如果num1的长度大于1
            if(len1 > 1) {
                temp[1] += tens;
                for(int n=1;n<len1;n++) 
                    sum[n-1] = temp[n] + sum[n];
            }               
        }
        //如果最后结果的长度大于len1，则还需要加上最后的sum
        for(int k=0;k<len1;k++) {
            int units = sum[k] % 10;
            int tens = sum[k] / 10;
            ans = units + ans;
            if(k!=len1-1) sum[k+1] = sum[k+1] + tens;
        }
        //去掉前面的0，直到第一位不是0或者只剩下1个0
        while(ans.length()>1 && ans.charAt(0) == '0') ans = ans.substring(1);
        return ans;                
    }
}