43. Multiply Strings

O(mn) time O(m+n) space

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        num = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            c = 0
            for j in range(n - 1, -1, -1):
                s = num[i + j + 1] + int(num1[i]) * int(num2[j]) + c
                c, num[i + j + 1] = divmod(s, 10)
            num[i] = c
        res = ''.join(map(str, num)).lstrip('0')
        return res if res else '0'

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.length(), n = num2.length();
        string res(m + n, '0');
        for (int i = m - 1, j; i >= 0; --i) {
            int c = 0;
            for (j = n - 1; j >= 0; --j) {
                int s = (res[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + c;
                res[i + j + 1] = s % 10 + '0';
                c = s / 10;
            }
            res[i] = c + '0';
        }
        int p = res.find_first_not_of("0");
        return p == string::npos ? "0" : res.substr(p);
    }
};