Multiply Strings 43 (LeetCode)

Question

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:

The numbers can be arbitrarily large and are non-negative.

Converting the input string to integer is NOT allowed.

You should NOT use internal library such as BigInteger.

Solution

创建一个len1+len2长度的数组用于存放结果，str1从最后往前每次取1位(i)，和str2的每一位(j)相乘，结果存在结果数组的i+j+1位上。有几点要注意：

1. str1的一位和str2的每一位相乘后，结果要加上数组在该位上保存的之前的结果和前一位的进位

2. 最高位有可能还需要进位

3. 结果数组是按最长结果开的，从后往前填可能并没有填满，所以要找到第一个不为0的数（即将开头的0都去掉）

代码如下：

public class Solution {
    public String multiply(String num1, String num2) {
        if(num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0){
            return "";
        }

        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }

        int len1 = num1.length();
        int len2 = num2.length();
        int len3 = len1 + len2;
        int[] num = new int[len3];
        int i, j, product, carrier;
        for(i = len1 - 1; i >= 0; i--){
            product = 0;
            carrier = 0;
            for(j = len2 - 1; j >= 0; j--){
            //str1的一位和str2的每一位相乘，结果加上数组在该位之前的结果，再加上前一位的进位
                product = carrier + num[i + j + 1] + Character.getNumericValue(num1.charAt(i)) * Character.getNumericValue(num2.charAt(j));
                carrier = product / 10;
                num[i + j + 1] = product % 10;
            }
            //考虑最高位还有进位
            num[i + j + 1] = carrier;
        }

        StringBuilder sb = new StringBuilder();
        i = 0;
        while(i < len3 - 1 && num[i] == 0){
            i++;
        }
        while(i < len3){
            sb.append(num[i++]);
        }

        return sb.toString();
    }
}