Multiply Strings LeetCode Solution | Easy Approach

Minimum Cost to Merge Stones
Share:

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.

Multiply Strings Solutions

Time: O(∣num1∣∣num2∣)
Space: um1∣+∣num2∣)

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 == -1 ? "0" : s.substr(i);
  }
};

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();
  }
}

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:]))

Watch Tutorial

Checkout more Solutions here

Leave a Comment

Your email address will not be published. Required fields are marked *

x