Multiply Strings

LeetCode Q 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:

• 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

Code:

public String multiply(String num1, String num2) {
  if (num1.equals("0") || num2.equals("0"))
    return "0";
  
  int len1 = num1.length(), len2 = num2.length();
  int[] num = new int[len1 + len2 - 1];

  for (int i = 0; i < len1; i++) {
    int n1 = num1.charAt(len1 - 1 - i) - '0';
    for (int j = 0; j < len2; j++) {
      int n2 = num2.charAt(len2 - 1 - j) - '0';
      res[i + j] += n1 * n2;
    }
  }

  StringBuilder sb = new StringBuilder();
  int carry = 0;
  for (int i = 0; i < index + 1; i++) {
    res[i] += carry;
    sb.append(res[i] % 10);
    carry = res[i] / 10;
  }
   
  if (carry != 0)
    sb.append(carry);
    
  return sb.reverse().toString();
}

Note if we don’t add the corner case in line 1, we have to deal with leading zeros in sb.

int index = len1 + len2 - 2;
while (index >= 0 && res[index] == 0) {
  index--;    
}
if (index == -1) return "0";