[Leetcode] 43. Multiply Strings

Looks like a simple problem. I thought to use Karatsuba algorithm to speed the program up, but it turns out not necessary - as the longest input will just be less than 180, then $O(180^2)$ is definitely good enough.

I briefly looked at some other people's hints and see that the key to this problem is that: num1[i] * num2[j] will be at final result's [i+j] position and [i+j+1] for the carrier.

---

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        n1, n2 = len(num1), len(num2)
        res = [0 for _ in range(n1+n2+1)]
        num1 = num1[::-1]
        num2 = num2[::-1]
        for i in range(n1):
            b1 = int(num1[i])
            for j in range(n2):
                b2 = int(num2[j])
                cur_b = res[i+j] + b1 * b2
                if cur_b <= 9:
                    res[i+j] = cur_b
                else:
                    res[i+j] = cur_b % 10
                    res[i+j+1] += cur_b / 10
        res = map(str, res)
        res = ''.join(res[::-1])
        i = 0
        while i < len(res) - 1 and res[i] == '0':
            i += 1
        return res[i:]