43. Multiply Strings

Math

class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }

        int n = num1.length(), m = num2.length();

        int [] result = new int[n + m];

        // multiply from the first digit
        for (int i = n - 1; i >= 0; i--) {
            int digit1 = num1.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int digit2 = num2.charAt(j) - '0';
                int product = digit1 * digit2;
                int sum = product + result[i + j + 1];

                result[i + j + 1] = sum % 10;           // current
                result[i + j] += sum / 10;              // carry
            }
        }

        // convert to string, pass the prefix 0
        StringBuilder sb = new StringBuilder();
        for (int num : result) {
            if (sb.length() == 0 && num == 0) continue;
            sb.append(num);
        }
        return sb.toString();

    }
}

Remarks:

1. TC: $O(m\times n)$ (m and n is the length of two strings); SC: $O(m+n)$ (result array).