[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.

Reference: https://drscdn.500px.org/photo/130178585/m%3D2048/300d71f784f679d5e70fadda8ad7d68f

Solution:  num1[i] * num2[j] will be placed at indices [i + j`, `i + j + 1]
class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null) return num2;
        if (num2 == null) return num1;
        
        if (num1.equals("0") || num2.equals("0")) return "0";
        
        int length1 = num1.length();
        int length2 = num2.length();
        int[] product = new int[length1 + length2];
        
        for (int i = length1 - 1; i >= 0; i--) {
            for (int j = length2 - 1; j >= 0; j--) {
                int multiply = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int pos = i + j;
                multiply += product[pos + 1];
                product[pos + 1] = multiply % 10;
                product[pos] += multiply / 10;
            }
        }
        
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < product.length; i++) {
            if (i == 0 && product[i] == 0)
                continue;
            result.append(Integer.toString(product[i]));
        }
                          
        return result.toString();
    }
}

TimeComplexity = O(m * n)