43. Multiply StringsLeetCode Solution

In this guide we will provide 43. Multiply StringsLeetCode Solution with best time and space complexity. The solution to Multiply Strings problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Table of Contents

43. Multiply StringsLeetCode Solution image

Problem Statement of Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”
Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”

Constraints:

1 <= num1.length, num2.length <= 200
num1 and num2 consist of digits only.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Complexity Analysis

  • Time Complexity: O(|\texttt{num1}||\texttt{num2}|)
  • Space Complexity: O(|\texttt{num1}| + |\texttt{num2}|)

43. Multiply StringsLeetCode Solution in C++

class Solution {
 public:
  string multiply(string num1, string num2) {
    string s(num1.length() + num2.length(), '0');

    for (int i = num1.length() - 1; i >= 0; --i)
      for (int j = num2.length() - 1; j >= 0; --j) {
        const int mult = (num1[i] - '0') * (num2[j] - '0');
        const int sum = mult + (s[i + j + 1] - '0');
        s[i + j] += sum / 10;
        s[i + j + 1] = '0' + sum % 10;
      }

    const int i = s.find_first_not_of('0');
    return i == string::npos ? "0" : s.substr(i);
  }
};
/* code provided by PROGIEZ */

43. Multiply StringsLeetCode Solution in Java

class Solution {
  public String multiply(String num1, String num2) {
    final int m = num1.length();
    final int n = num2.length();

    StringBuilder sb = new StringBuilder();
    int[] pos = new int[m + n];

    for (int i = m - 1; i >= 0; --i)
      for (int j = n - 1; j >= 0; --j) {
        final int multiply = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
        final int sum = multiply + pos[i + j + 1];
        pos[i + j] += sum / 10;
        pos[i + j + 1] = sum % 10;
      }

    for (final int p : pos)
      if (p > 0 || sb.length() > 0)
        sb.append(p);

    return sb.length() == 0 ? "0" : sb.toString();
  }
}
// code provided by PROGIEZ

43. Multiply StringsLeetCode Solution in Python

class Solution:
  def multiply(self, num1: str, num2: str) -> str:
    s = [0] * (len(num1) + len(num2))

    for i in reversed(range(len(num1))):
      for j in reversed(range(len(num2))):
        mult = int(num1[i]) * int(num2[j])
        summ = mult + s[i + j + 1]
        s[i + j] += summ // 10
        s[i + j + 1] = summ % 10

    for i, c in enumerate(s):
      if c != 0:
        break

    return ''.join(map(str, s[i:]))
#code by PROGIEZ

Additional Resources

See also  33. Search in Rotated Sorted Array LeetCode Solution

Feel free to give suggestions! Contact Us