43. Multiply Strings (Medium) Facebook Twitter

Given two non-negative integersnum1andnum2represented as strings, return the product ofnum1andnum2.

Note:

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

Solution 1: Math O(m * n); O(m + n)

Remember how we do multiplication?

Start from right to left, perform multiplication on every pair of digits, and add them together.
Let’s draw the process! From the following draft, we can immediately conclude:

 `num1[i] * num2[j]` will be placed at indices `[i + j`, `i + j + 1]`

    /**
     * Start from right to left, multiply each pair of digits, and add them together.
     * The result of num1[i] * num2[j] will be placed at i + j and i + j + 1.
     */
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) {
            return "";
        }
        if (num1.length() == 0 || num2.length() == 0 || num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int m = num1.length();
        int n = num2.length();
        int[] product = new int[m + n];
        for (int i = m - 1; i >= 0; i--) { //num2 * num1
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = mul + product[p2];
                product[p1] += sum / 10; //原来的+现在的，i=m-1时，num[p1] = 0;
                product[p2] = sum % 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int p : product) {
            if (p != 0 || sb.length() != 0) {
                sb.append(p);
            }
        }
        return sb.toString();
    }