<p>Given two non-negative integers <code>num1</code> and <code>num2</code> represented as strings, return the product of <code>num1</code> and <code>num2</code>, also represented as a string.</p>

<p><strong>Note:</strong>&nbsp;You must not use any built-in BigInteger library or convert the inputs to integer directly.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> num1 = "2", num2 = "3"
<strong>Output:</strong> "6"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> num1 = "123", num2 = "456"
<strong>Output:</strong> "56088"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num1.length, num2.length &lt;= 200</code></li>
	<li><code>num1</code> and <code>num2</code> consist of digits only.</li>
	<li>Both <code>num1</code> and <code>num2</code>&nbsp;do not contain any leading zero, except the number <code>0</code> itself.</li>
</ul>

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        # Base case for recursion (single digit multiplication)
        if len(num1) == 1 and len(num2) == 1:
            return str(int(num1) * int(num2))
        
        # Make the number of digits the same by prepending zeros
        d = max(len(num1), len(num2))
        
        # If the number of digits is odd, make it even by padding with a zero
        if d % 2 != 0:
            d += 1
        
        num1 = num1.zfill(d)  # Add leading zeros if needed - OR - 
        num2 = '0'*(d - len(num2)) + num2
        
        # Split the numbers into two halves
        xh, xl = num1[:d//2], num1[d//2:]
        yh, yl = num2[:d//2], num2[d//2:]
        
        # Recursively calculate the three products using Karatsuba's formula
        s1 = self.multiply(xh, yh)  # s1 = xh * yh
        s2 = self.multiply(xl, yl)  # s2 = xl * yl
        
        temp1 = str(int(xh) + int(xl)) 
        temp2 = str(int(yh) + int(yl))
        s3 = self.multiply(temp1, temp2)  # s3 = (xh + xl) * (yh + yl)
        
        s4 = str(int(s3) - int(s2) - int(s1))  # s4 = s3 - s2 - s1
        
        # Combine the results: s1 * 10^d + s4 * 10^(d/2) + s2
        return str(int(s1) * (10**d) + int(s4) * (10**(d//2)) + int(s2))
    
16700