Problem description:

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

Example 1:

1
2
Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

1
2
Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution:

Things to note:

  1. The product of two numbers cannot exceed the sum of the two lengths. (e.g. 99 * 99 cannot be five digit)
  2. The position of result:
    1
    2
    3
    int d1 = num1.charAt(i) - '0';
    int d2 = num2.charAt(j) - '0';
    products[i + j + 1] += d1 * d2;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        m, n = len(num1), len(num2)
        result = [0] * (m + n)
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                mul = (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
                posLow = i + j + 1
                posHigh = i + j
                mul += result[posLow]
                result[posLow] = mul % 10
                result[posHigh] += mul // 10
        # e.g., num1='123', num2='456'; then result = [0, 5, 6, 0, 8, 8], res = [5, 6, 0, 8, 8]
        print(result)
        sb = []
        for res in result:
            print(res)
            if len(sb) != 0 or res != 0: # deal with leading zero issue
                sb.append(res)
            print(sb)
            print("------")
        return "0" if len(sb) == 0 else ''.join(str(s) for s in sb)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string multiply(string num1, string num2) {
        /*
        1. the length of result string is (num1.length+ num2.length)
        
        */
        
        string res(num1.length()+num2.length(), '0');
        for(int i= num1.size()-1; i>= 0; i--){
            int carry= 0;
            for(int j= num2.size()-1; j>= 0; j--){
                int tmp= (res[i+j+1]- '0')+ (num1[i]-'0')* (num2[j]-'0')+ carry;
                res[i+j+1] = tmp%10+'0'; //because i and j both starts at size-1
                carry= tmp/10;
            }
            res[i]+= carry;
        }
        
        
        size_t startpos = res.find_first_not_of("0");
        if (string::npos != startpos) {
            return res.substr(startpos);
        }
        return "0";
        
        
    }
};

time complexity: $O()$
space complexity: $O()$
reference: