43. Multiply Strings – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 43. Multiply Strings:-

https://leetcode.com/problems/multiply-strings

Brute Force: Convert and Multiply O(m + n)

The simplest approach is to convert both strings into numbers, multiply them, and convert the result back into a string.

We can construct the numbers ourselves by multiplying the current number by 10 and adding the next digit.

But this fails the restrictions.

class Solution {
public:
    string multiply(string num1, string num2) {
        long long n1 = 0, n2 = 0;

        for(char c : num1)
            n1 = n1 * 10 + (c - '0');

        for(char c : num2)
            n2 = n2 * 10 + (c - '0');

        long long product = n1 * n2;

        if(product == 0)
            return "0";

        string ans = "";

        while(product > 0) {
            int digit = product % 10;
            ans += ('0' + digit);
            product /= 10;
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }
};
43. Multiply Strings Naive Solution

Optimal: O(m × n)

We can simply simulate the multiplication we do on paper.

For example:

      123
    × 456
    -------
      738
     6150
    49200
    -------
    56088

Instead of creating separate rows and adding them, we can directly store the result in an array.

Let’s take 123 × 456.

The maximum size of the result can be m + n, where m and n are the lengths of the two strings.

So we create an array of size m + n, initially filled with zeroes.

vector<int> res(m + n, 0);

Now, multiply every digit of num1 with every digit of num2, starting from the right.

The important part is where we store the result.

For digits at indices i and j:

  • i + j + 1 stores the current digit.
  • i + j stores the carry.
int sum = (num1[i] - '0') * (num2[j] - '0') + res[i + j + 1];

res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;

We use % 10 to get the current digit and / 10 to get the carry.

After processing all pairs of digits, we just convert the result array into a string, skipping any leading zeroes.

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

        int m = num1.size();
        int n = num2.size();

        vector<int> res(m + n, 0);

        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {

                int sum = (num1[i] - '0') * (num2[j] - '0') + res[i + j + 1];

                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }

        string ans = "";
        int i = 0;

        // Skip leading zeros
        while(i < res.size() && res[i] == 0)
            i++;

        while(i < res.size()) {
            ans += to_string(res[i]);
            i++;
        }

        return ans;
    }
};
43. Multiply Strings Optimal Solution

43. Multiply Strings 43. Multiply Strings 43. Multiply Strings 43. Multiply Strings 43. Multiply Strings

Leave a Reply