43. Multiply Strings

Problem

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.

Solution (Java)

class Solution {
    private int[] getIntArray(String s) {
        char[] chars = s.toCharArray();
        int[] arr = new int[chars.length];
        for (int i = 0; i < chars.length; i++) {
            arr[i] = chars[i] - '0';
        }
        return arr;
    }

    private String convertToStr(int[] res, int i) {
        char[] chars = new char[res.length - i];
        int k = 0;
        for (; i < res.length; i++) {
            chars[k] = (char) (res[i] + '0');
            k++;
        }
        return new String(chars);
    }

    public String multiply(String num1, String num2) {
        int[] arr1 = getIntArray(num1);
        int[] arr2 = getIntArray(num2);
        int[] res = new int[arr1.length + arr2.length];
        int index = arr1.length + arr2.length - 1;
        for (int i = arr2.length - 1; i >= 0; i--) {
            int k = index--;
            for (int j = arr1.length - 1; j >= 0; j--) {
                res[k] += arr2[i] * arr1[j];
                k--;
            }
        }
        index = arr1.length + arr2.length - 1;
        int carry = 0;
        for (int i = index; i >= 0; i--) {
            int temp = res[i] + carry;
            res[i] = temp % 10;
            carry = temp / 10;
        }
        int i = 0;
        while (i < res.length && res[i] == 0) {
            i++;
        }

        if (i > index) {
            return "0";
        } else {
            return convertToStr(res, i);
        }
    }
}

Solution (Javascript)

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
  var len1 = num1.length;
  var len2 = num2.length;
  var res = Array(len1 + len2).fill(0);
  var carry = 0;
  var val = 0;
  var index = 0;

  for (var i = len1 - 1; i >= 0; i--) {
    carry = 0;
    for (var j = len2 - 1; j >= 0; j--) {
      index = len1 + len2 - 2 - i - j;
      val= (num1[i] * num2[j]) + carry + res[index];
      carry = Math.floor(val / 10);
      res[index] = val % 10;
    }
    if (carry) res[index + 1] = carry;
  }

  while (res.length > 1 && res[res.length - 1] === 0) res.pop();

  return res.reverse().join('');
};

Explain:

nope.

Complexity:

• Time complexity : O(m*n).
• Space complexity : O(log(m*n)).