Leetcode 43. Multiply Strings

Problem Explanation:

The problem involves two input strings which represent non-negative integers. The task is to return the product of these two integers as a string. While the most straightforward way to achieve this is by converting the strings to integers, performing the multiplication, and then converting the result back to a string, the problem specifically disallows this approach. Therefore, we need to come up with a different method.

In a numerical operation, the multiplication of two numbers, say a string of length m and a string of length n, can lead to a result having a length from m+n-1 to m+n. Hence we initialize a string of size m+n with all elements as '0'.

Let's take an example to understand the solution,

num1: "123" num2: "456"

Expected output: 123*456 = "56088"

We will start from num1's last element and for each element in num1, we will start from num2's last element till the first element. For each such pair of elements, we calculate the product and get the current sum by adding product to the corresponding index in our result string. At last, we fill the sum/10 in the lower index and sum%10 in the current index of our result string.

Solution:

Python

1
2python
3class Solution:
4    def multiply(self, num1: str, num2: str) -> str:
5        m, n = len(num1), len(num2)
6        pos = [0] * (m + n)
7        
8        for i in range(m-1, -1, -1):
9            for j in range(n-1, -1, -1):
10                mul = int(num1[i]) * int(num2[j])
11                p1, p2 = i + j, i + j + 1
12                
13                sum = mul + pos[p2]
14
15                pos[p1] += sum // 10
16                pos[p2] = sum % 10
17
18        result = ''.join(map(str, pos)).lstrip('0')
19        return result if result else '0'

Java

1
2java
3class Solution {
4    public String multiply(String num1, String num2) {
5        int m = num1.length(), n = num2.length();
6        int[] pos = new int[m + n];
7
8        for (int i = m - 1; i >= 0; i--) {
9            for (int j = n - 1; j >= 0; j--) {
10                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
11                int p1 = i + j, p2 = i + j + 1;
12                int sum = mul + pos[p2];
13
14                pos[p1] += sum / 10;
15                pos[p2] = sum % 10;
16            }
17        }
18
19        StringBuilder sb = new StringBuilder();
20        for (int p : pos) if (!(sb.length() == 0 && p == 0)) sb.append(p);
21        return sb.length() == 0 ? "0" : sb.toString();
22    }
23}

Javascript

1
2javascript
3var multiply = function(num1, num2) {
4    let m = num1.length, n = num2.length, pos = Array(m+n).fill(0); 
5
6    for (let i = m - 1; i >= 0; i--) {
7        for (let j = n - 1; j >= 0; j--){
8            let mul = (num1[i] - '0') * (num2[j] - '0');
9            let p1 = i + j, p2 = i + j + 1;
10            let sum = mul + pos[p2]; 
11
12            pos[p1] += Math.floor(sum / 10); 
13            pos[p2] = sum % 10; 
14        }
15    }
16
17    while (pos[0] == 0) pos.shift();
18    return pos.length == 0 ? "0" : pos.join('');
19};

C++

1
2c++
3class Solution {
4public:
5    string multiply(string num1, string num2) {
6        string product(num1.size() + num2.size(), '0');
7        reverse(num1.begin(), num1.end());
8        reverse(num2.begin(), num2.end());
9        for(int i = 0; i < num1.size(); i++) {
10            for(int j = 0; j < num2.size(); j++) {
11                product[i + j] += (num1[i] - '0') * (num2[j] - '0');
12                product[i + j + 1] += product[i + j] / 10;
13                product[i + j] %= 10;
14            }
15        }
16        while(product.size() > 1 && product.back() == '0') product.pop_back();
17        reverse(product.begin(), product.end());
18        for(auto &c : product) c += '0';
19        return product;
20    }
21};

C#

1
2csharp
3public class Solution {
4    public string Multiply(string num1, string num2) {
5        int m = num1.Length, n = num2.Length;
6        int[] pos = new int[m + n];
7 
8        for(int i = m - 1; i >= 0; i--) {
9            for(int j = n - 1; j >= 0; j--) {
10                int mul = (num1[i] - '0') * (num2[j] - '0');
11                int p1 = i + j, p2 = i + j + 1;
12                int sum = mul + pos[p2];
13                pos[p1] += sum / 10;
14                pos[p2] = sum % 10;
15            }
16        }  
17        StringBuilder sb = new StringBuilder();
18        foreach(int p in pos) if(!(sb.Length == 0 && p == 0)) sb.Append(p);
19        return sb.Length == 0 ? "0" : sb.ToString();
20    }
21}

In the solution provided, we are considering each digit of both input strings, calculating the product of them and adding the result at the appropriate index of the result string. We are also making sure that only the unit's place of the calculated product remains at the corresponding index in the result string and the remaining part is carried forward to be added at a subsequent index.This method ensures that the multiplication is done in the same manner as we do it manually, thereby not exceeding the integer limit in case of long strings as inputs.

This solution is implemented in Python, JavaScript, Java, C++ and C#. In Python, the entire solution is defined within a single function called 'multiply'. It starts by initializing an array 'pos' filled with zeros whose length is the sum of the lengths of both input strings. For each pair of digits from the input strings, their product is calculated and added to the element of 'pos' at the corresponding index. Repeated addition operations are performed until every pair of digits is covered. A string is created from 'pos', removing the trailing zeros and returned.

In JavaScript, we iterate over the characters in both input strings from right to left and then calculate the product of each pair. Each calculated product is divided by 10 to strip off the unit’s place and then the result is stored in an array 'pos'. After this, the array is converted into a string which is the final result.

In Java, we doing almost the same as Python and Javascript. We defined a string builder from which we append the product of every pair and return the string after stripping it off the leading zeros.

C# and C++ solutions use the same approach with comparable code that follows the same logic as the other languages. In the C++ implementation, we use the 'reverse' function to reverse the input strings before processing them. After computing the product string, we reverse it again to obtain the result in the right order.

This problem is an excellent example of how string manipulation techniques can be used to perform numerical operations while bypassing language limitations concerning numerical data types. Moreover, it is a pretty efficient solution as its time complexity is O(m*n) where m and n are the lengths of the input strings num1 and num2, respectively. It is because for each digit in num1, we are iterating through each digit in num2.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫