Multiply Strings

How it works

Instead of generating partial products and adding them as separate strings, we can use a single result array to accumulate all digit multiplications in place. When we multiply digit i of num1 by digit j of num2, the result contributes to position i + j in the final answer. By reversing both strings first, we can work with indices that naturally align with place values. After processing all digit pairs, we handle carries and convert the result array back to a string.

Steps

1. If either number is "0", return "0" immediately.
2. Create a result array of size len(num1) + len(num2) initialized to zeros.
3. Reverse both input strings so index 0 corresponds to the ones place.
4. For each pair of indices (i1, i2):
   • Multiply the corresponding digits.
   • Add the product to res[i1 + i2].
   • Propagate any carry to res[i1 + i2 + 1].
   • Keep only the ones digit at res[i1 + i2].
5. Reverse the res array, skip leading zeros, and join the digits into a string.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(m + n)

Where m is the length of the string num1 and n is the length of the string num2.

Things to watch for

Not Handling the Zero Case

When either input is "0", the result must be "0". Failing to check this upfront can lead to returning an empty string or a string with leading zeros. Always check for zero inputs before proceeding with multiplication to avoid unnecessary computation and incorrect output formatting.

Incorrect Position Indexing for Digit Products

When multiplying digit i of num1 by digit j of num2, the result contributes to a specific position in the output array. If strings are reversed, the position is i + j; if not, careful index calculation is needed. Off-by-one errors in position calculation cause digits to be placed incorrectly, resulting in a wrong final product.

Forgetting to Handle Leading Zeros in the Result

After populating the result array, there may be leading zeros (especially at the highest index positions after reversing). Skipping these zeros before converting to a string is essential. However, if all digits are zero (which should not happen if the zero case is handled), ensure at least one "0" is returned rather than an empty string.

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if "0" in [num1, num2]:
            return "0"

        res = [0] * (len(num1) + len(num2))
        num1, num2 = num1[::-1], num2[::-1]
        for i1 in range(len(num1)):
            for i2 in range(len(num2)):
                digit = int(num1[i1]) * int(num2[i2])
                res[i1 + i2] += digit
                res[i1 + i2 + 1] += res[i1 + i2] // 10
                res[i1 + i2] = res[i1 + i2] % 10

        res, beg = res[::-1], 0
        while beg < len(res) and res[beg] == 0:
            beg += 1
        res = map(str, res[beg:])
        return "".join(res)

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0") {
            return "0";
        }

        vector<int> res(num1.length() + num2.length(), 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        for (int i1 = 0; i1 < num1.length(); i1++) {
            for (int i2 = 0; i2 < num2.length(); i2++) {
                int digit = (num1[i1] - '0') * (num2[i2] - '0');
                res[i1 + i2] += digit;
                res[i1 + i2 + 1] += res[i1 + i2] / 10;
                res[i1 + i2] %= 10;
            }
        }

        stringstream result;
        int i = res.size() - 1;
        while (i >= 0 && res[i] == 0) {
            i--;
        }
        while (i >= 0) {
            result << res[i--];
        }
        return result.str();
    }
};