[Python] Coding Interview Patterns: Unpublished Lessons/

...

/

Solution: Multiply Strings

Solution: Multiply Strings

Let’s solve the Multiply Strings problem using the Math and Geometry pattern.

We'll cover the following...

Statement

Given two non-negative integers, str1 and str2 represented as strings, return the product of these integers result, which is also represented as a string.

Constraints:

  • str1 and str2 consist of digits only.
  • 1≤1 \leq str1.length, str2.length ≤200\leq 200
  • No leading 00 in str1 or str2.

Solution

The first solution that comes to mind would be using the traditional elementary school algorithm for multiplying two numbers, str1 and str2. We start by multiplying each digit of str2 with str1, storing the multiplication results, and adding them at the end. Before performing addition, we append zeros to the right of each of these intermediate results depending upon the position of the multiplier digit in str2, which is a computationally expensive process. This method is also costly in terms of space complexity as it requires saving str2.length intermediate results. The maximum size of the last intermediate results would be (m+n−1)(m+n-1), where ...