[LeetCode] 43. Multiply Strings

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

Note:

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

Thought process:

Use an array to keep track of the products of each pair of digits and add them together. When doing multiplication, I need to align the numbers to the right. So I need to iterate through the product array from right to left.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public String multiply(String num1, String num2) { int[] products = new int[num1.length() + num2.length() - 1]; for (int i = num1.length() - 1; i >= 0; i--) { for (int j = num2.length() - 1; j >= 0; j--) { products[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0'); } } int i = products.length - 1; int carry = 0; StringBuilder sb = new StringBuilder(); while (i >= 0 || carry > 0) { int sum = i >= 0 ? products[i] + carry : carry; sb.append(sum % 10); carry = sum / 10; i--; } while (sb.length() > 0 && sb.charAt(sb.length() - 1) == '0') { sb.deleteCharAt(sb.length() - 1); } return sb.length() == 0 ? "0" : sb.reverse().toString(); } }

Time complexity:
Say num1.length = a and num2.length = b. The overall time complexity is O(ab).