43. Multiply Strings - cocoder39/coco39_LC GitHub Wiki

43. Multiply Strings

• length of final result
  • eg. 999 * 99 < 1000 * 100 = 100,000
  • m-digit * n-digit < 10^m * 10^n = 10^(m+n) ==>>
  • m-digit * n-digit <= 10^(m+n) - 1 = (m+n)-digit
• attention to leading 0
  • attention to empty string after removing leading 0, which should be mapped to 0
• once reverse num1, num2, res[i+j] += int(num1[i]) * int(num2[j])

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        res = [0] * (m+n)

        num1, num2 = num1[::-1], num2[::-1]
        for i in range(m): 
            for j in range(n):
                res[i+j] += int(num1[i]) * int(num2[j])
                res[i+j+1] += res[i+j] // 10
                res[i+j] %= 10 
        
        res.reverse()
        start = 0
        while start < len(res) and res[start] == 0:
            start += 1

        if start == len(res):
            return '0'

        return ''.join([str(digit) for digit in res[start:]])

m-digit number * n-digit number = (m+n)-digit number

eg. 999 * 99 < 1000 * 100 = 100,000
m-digit * n-digit < 10^m * 10^n = 10^(m+n) ==>> 
m-digit * n-digit <= 10^(m+n) - 1 = (m+n)-digit

corner case: leading '0'

string multiply(string num1, string num2) {
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        
        int m = num1.length(), n = num2.length();
        string res(m + n, '0');
        
        for (int i = 0; i < m; i++) {
            int carry = 0;
            for (int j = 0; j < n; j++) {
                int sum = res[i + j] - '0' + (num1[i] - '0') * (num2[j] - '0') + carry;
                res[i + j] = sum % 10 + '0';
                carry = sum / 10;
            }
            res[i + n] = carry + '0';
        }
        
        while (res.size() > 1 && res.back() == '0') res.pop_back();
        reverse(res.begin(), res.end());
        return res;
    }