Multiply Strings

120.Multiply Strings

String

Simulation

Problem Statement:

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also as a string. Note:

• The input strings do not contain leading zeros except for the number "0" itself.
• You must not use any built-in BigInteger library or convert the inputs to integers directly.

Algorithm:

1. Initialize an array pos of size m + n to store intermediate results, where m and n are the lengths of num1 and num2.
2. Iterate through each digit of num1 and num2 from right to left, multiplying the digits and adding the results to the corresponding positions in pos.
3. Update the carry-over for each position to ensure the result is correctly aligned.
4. Construct the result string from pos, skipping leading zeros.
5. Return the result string, or "0" if no digits were added to the string builder.

Complexity:

Time: O(m × n), where m and n are the lengths of num1 and num2 | Space: O(m + n).

Java Implementation:

public class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + pos[p2];

                pos[p2] = sum % 10;
                pos[p1] += sum / 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int p : pos) if (!(sb.length() == 0 && p == 0)) sb.append(p);
        return sb.length() == 0 ? "0" : sb.toString();
    }
}
                

Python Implementation:

def multiply(num1, num2):
    m, n = len(num1), len(num2)
    pos = [0] * (m + n)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
            p1, p2 = i + j, i + j + 1
            sum_ = mul + pos[p2]

            pos[p2] = sum_ % 10
            pos[p1] += sum_ // 10

    result = ''.join(map(str, pos)).lstrip('0')
    return result if result else "0"
                

C++ Implementation:

#include 
#include 
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        vector pos(m + n, 0);

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + pos[p2];

                pos[p2] = sum % 10;
                pos[p1] += sum / 10;
            }
        }

        string result;
        for (int p : pos) {
            if (!(result.empty() && p == 0)) result.push_back(p + '0');
        }
        return result.empty() ? "0" : result;
    }
};