43. Multiply Strings

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:

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

Solution

(1) Java

class Solution {
    public String multiply(String num1, String num2) {
        int len = num1.length() + num2.length();
        char[] ca1 = num1.toCharArray();
        char[] ca2 = num2.toCharArray();
        char[] rst = new char[len];
        Arrays.fill(rst, '0');
        for (int i = ca2.length-1; i >= 0; i--) {
            char c2 = ca2[i];
            int carry = 0;
            for (int j = ca1.length-1; j >= 0; j--) {
                char c1 = ca1[j];
                int c = (c2-'0')*(c1-'0')+Character.getNumericValue(rst[i+j+1])+carry;
                rst[i+j+1] = (char)('0' + c%10);
                carry = c/10;
            }
            int k = i;
            while (carry != 0) {
                int num = rst[k]-'0'+carry;
                rst[k] = (char)('0'+num%10);
                carry = num/10;
                k--;
            }
        }
        for (int i = 0; i < len; i++) {
            if (rst[i] != '0') {
                String rstStr = new String(rst);
                return rstStr.substring(i);
            }
        }
        return new String("0");
    }
}

(2) Python

class Solution:
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        m = len(num1)
        n = len(num2)
        rst = [0]*(m+n)
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                p = int(num1[i])*int(num2[j]) + rst[i+j+1]
                rst[i+j+1] = p%10
                rst[i+j] += (int)(p/10)
        for i in range(0, m+n):
            if rst[i] != 0:
                rst = rst[i:]
                rst2 = ''
                for idx, i in enumerate(rst):
                    rst2 += str(i);
                return rst2
        return '0'

(3) Scala