The problem Multiply Strings Leetcode solution asks us to multiply two strings which are given to us as input. We are required to print or return this result of multiplying to the caller function. So to put it more formally given two strings, find the product of the given strings. These strings can have many digits. So one should not try to simply convert the given strings into integers and then use simple multiplication. Let’s take a look at a few examples for better understanding.
Table of Contents
Examples
First String: "2" Second String: "3"
Resultant String: "6"
Explanation: Since both the strings have only single digits. We can check that the output should have been 6 and that is the case.
First String: "123" Second String: "456"
Resultant String: "56088"
Explanation: In this example also, we are provided with two strings, which are then multiplied to give “56088”.
First String: "123" Second String: "0"
Resultant String: "0"
Explanation: Here we did not print “000” or “00”. In case, when the result is 0, we are required to print a single “0”.
First String: "123456789" Second String: "987654321123456789987"
Resultant String: "121932631127876847872042371743"
Explanation: Now, in this example, we are given two strings that are multiplied to give a large string as output which could not have been saved in a numeric data type. So, this example is one of the few that our algorithm should be able to deal with.
Brute Force Approach for Multiply Strings Leetcode Solution
The problem Multiply Strings Leetcode Solution simply asked us to multiply two given strings. So, why don’t we do just that? Well, it’s a bit tricky to successfully implement it. But, if you recall how we used to multiply two numbers we can easily use the same technique here.
So, in this approach, we will traverse over one of the given strings from right to left. When we are at an index or a character, we multiply whole of the other string with this current character. Once we are done with our multiplication, we add zeroes to the end of it. The number of zeroes that are to be added equals the position of the current character in its string from the end – 1. Once we are done with adding zeroes, we add this string to the result. So, as we have traversed from right to left of the first string, the resultant string stores the answer.
Brute Force Code
C++ code for Multiply Strings Leetcode Solution
#include <bits/stdc++.h>
using namespace std;
inline string add_zero(int n){
string res = "";
while(n-- > 0)res += "0";
return res;
}
string add_string(string& a, string& b){
if(a.size()>b.size())swap(a,b);
int a_len = a.size(), b_len = b.size();
string res = "";
int sum = 0, carry = 0;
for(int i=0;i<b_len;i++){
int a_idx = a_len-1-i, b_idx = b_len-1-i;
sum = carry + (a_idx>=0 ? (a[a_idx]-'0') : 0) + (b[b_idx]-'0');
carry = sum/10; sum %= 10;
res += to_string(sum);
}
if(carry>0)
res += to_string(carry);
reverse(res.begin(), res.end());
return res;
}
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
string res = "";
if(num1.size()>num2.size())swap(num1, num2);
int num1_len = num1.size(), num2_len = num2.size();
for(int i=num1_len-1;i>=0;i--){
int multiplier = num1[i]-'0';
int sum = 0, carry = 0;
string cur_res = "";
for(int j=num2_len-1;j>=0;j--){
sum = carry + (num2[j]-'0')*multiplier;
carry = sum/10; sum %= 10;
cur_res += to_string(sum);
}
if(carry>0)
cur_res += to_string(carry);
reverse(cur_res.begin(), cur_res.end());
cur_res += add_zero(num1_len-i-1);
res = add_string(res, cur_res);
}
return res;
}
int main(){
string num1 = "123";
string num2 = "456";
cout<<multiply(num1, num2);
}
56088
Java code for Multiply Strings Leetcode Solution
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
private static String add_zero(int n){
String res = "";
while(n-- > 0)res += "0";
return res;
}
private static String add_string(String a, String b){
if(a.length()>b.length()){
String tmp = a;
a = b;
b = tmp;
}
int a_len = a.length(), b_len = b.length();
String res = "";
int sum = 0, carry = 0;
for(int i=0;i<b_len;i++){
int a_idx = a_len-1-i, b_idx = b_len-1-i;
sum = carry + (a_idx>=0 ? (a.charAt(a_idx)-'0') : 0) + (b.charAt(b_idx)-'0');
carry = sum/10; sum %= 10;
res += Integer.toString(sum);
}
if(carry>0)
res += Integer.toString(carry);
StringBuilder sb = new StringBuilder(res);
sb.reverse();
return sb.toString();
}
public static String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0"))
return "0";
String res = "";
if(num1.length()>num2.length()){
String tmp = num1;
num1 = num2;
num2 = tmp;
}
int num1_len = num1.length(), num2_len = num2.length();
for(int i=num1_len-1;i>=0;i--){
int multiplier = num1.charAt(i)-'0';
int sum = 0, carry = 0;
String cur_res = "";
for(int j=num2_len-1;j>=0;j--){
sum = carry + (num2.charAt(j)-'0')*multiplier;
carry = sum/10; sum %= 10;
cur_res += Integer.toString(sum);
}
if(carry>0)
cur_res += Integer.toString(carry);
StringBuilder sb = new StringBuilder(cur_res);
sb.reverse();
sb.append(add_zero(num1_len-i-1));
res = add_string(res, sb.toString());
}
return res;
}
public static void main(String[] args){
String num1 = "123";
String num2 = "456";
System.out.println(multiply(num1, num2));
}
}56088
Complexity Analysis
Time Complexity
O(N*M), where N is the size of the first string and M is the size of the second string.
Space Complexity
O(N+M), since we stored the result in a separate string that can have a size of N+M. Thus space complexity is linear.
Optimized Approach for Multiply Strings Leetcode Solution
The optimized approach is a bit tricky to observe in the first go. The optimized approach also has the same time complexity as the above brute force approach but removes the overhead cost of reversing the string and addition of each intermediate resultant string to the answer. In the optimized approach, we multiply each of the digits of both the strings. Thus, we consider each pair of indices, one index from the first string and the other from the second string. The idea is that if the indices are i, j in first and second string respectively, they attain i+j, i+j+1 indices in the resultant string. So using this fact, we can remove the overhead which was being lost in adding the intermediate strings, adding zeroes, reversing intermediate strings which speed up the solution drastically. Looking at the image below will make it better to understand.
Optimized code
C++ code for Multiply Strings Leetcode Solution
#include <bits/stdc++.h>
using namespace std;
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0")
return "0";
if(num1.size()>num2.size())swap(num1, num2);
int num1_len = num1.size(), num2_len = num2.size();
int res[num1_len+num2_len];memset(res, 0, sizeof res);
for(int i=num1_len-1;i>=0;i--){
for(int j=num2_len-1;j>=0;j--){
int p1 = i+j, p2 = p1+1;
int sum = (num1[i]-'0')*(num2[j]-'0') + res[p2];
res[p2] = sum%10;
res[p1] += sum/10;
}
}
string output = ""; int idx = -1;
for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
idx = i;
for(int i=idx+1;i<num1_len+num2_len;i++)
output += to_string(res[i]);
return output;
}
int main(){
string num1 = "123";
string num2 = "456";
cout<<multiply(num1, num2);
}
56088
Java Code for Multiply Strings Leetcode Solution
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
public static String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0"))
return "0";
if(num1.length()>num2.length()){
String tmp = num1;
num1 = num2;
num2 = tmp;
}
int num1_len = num1.length(), num2_len = num2.length();
int res[] = new int[num1_len+num2_len];
Arrays.fill(res, 0);
for(int i=num1_len-1;i>=0;i--){
for(int j=num2_len-1;j>=0;j--){
int p1 = i+j, p2 = p1+1;
int sum = (num1.charAt(i)-'0')*(num2.charAt(j)-'0') + res[p2];
res[p2] = sum%10;
res[p1] += sum/10;
}
}
String output = ""; int idx = -1;
for(int i=0;i<num1_len+num2_len && res[i] == 0;i++)
idx = i;
for(int i=idx+1;i<num1_len+num2_len;i++)
output += Integer.toString(res[i]);
return output;
}
public static void main(String[] args){
String num1 = "123";
String num2 = "456";
System.out.println(multiply(num1, num2));
}
}56088
Complexity Analysis
Time Complexity
O(N*M), even though the complexity is the same as the brute force method, removing the overhead costs improves the performance drastically.
Space Complexity
O(N+M), because the size of the resultant string is N+M, where N is the size of the first string, and M is the size of the second string.