LeetCode-Multiply Strings

Description：

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"      

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"      

Note:

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contain only digits 0-9.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

• 我们首先将两个字符串转为两个整数数组digit1和digit2（逆序，这样低位在首部）；
• 之后，我们进行乘法运算，，即对digit2中的所有每一个元素，都乘以digit1中的所有元素存储在对应位置上（注意，此时并没有累加进位）；
• 现在，我们需要对所得的结果result进行进位的累加，对每个大于等于10的元素，累加进位到后一个元素上，并且当前位进行取余；
• 最后，我们需要跳过result中的前导0后得到result有效数字的长度，逆序取出即是最后的结果；

Java

class Solution {
    public String multiply(String num1, String num2) {
        int[] digit1 = new int[num1.length()];
        int[] digit2 = new int[num2.length()];
        int[] result = new int[num1.length() + num2.length() + 1];
        
        for (int i = num1.length() - 1, j = 0; i >= 0; i--) digit1[j++] = num1.charAt(i) - '0';
        for (int i = num2.length() - 1, j = 0; i >= 0; i--) digit2[j++] = num2.charAt(i) - '0';
        
        for (int i = 0; i < digit1.length; i++) {
            for (int j = 0; j < digit2.length; j++) {
                result[i + j] += digit1[i] * digit2[j];
            }
        }
        for (int i = 0; i < result.length; i++) {
            if (result[i] >= 10) {
                result[i + 1] += result[i] / 10;
                result[i] %= 10;
            }
        }
        int len = result.length - 1;
        while (len >= 0 && result[len] == 0) len--;
        StringBuilder num = new StringBuilder();
        while (len >= 0) num.append(result[len--]);
        
        return num.length() == 0 ? "0" : num.toString();
    }
}