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:

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

Example 2:

 12 Input: num1 = "123", num2 = "456" Output: "56088" 

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

Related Topics:StringMath

## 解題邏輯與實作

1. m 位數與 n 位數相乘，結果最大為 m+n 位
2. n1[i] 與 n2[j] 相乘結果會出現在 answer[i+j]上 ← 忘了說，這條是因為我把乘數與被乘數反轉才成立的
3. corner case ：任何與 0 相乘都會是 0 ，所以遇到是 0 可以直接回傳了

1. 判斷乘數與被乘數是否 0 ，若任一數為 0 ，則回傳答案為 0 ，否則繼續向下執行。
2. 反轉乘數與被乘數，方便從最低位數開始計算。
3. 使用雙層迴圈，依序取值，兩相乘後與進位值和上一層相乘結果相加。
4. 最後將計算結果反轉後回傳。
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 class Solution: def __init__(self): self.acrii_0 = ord('0') def chr_to_int(self,num): return ord(num) - self.acrii_0 def int_to_chr(self,num): return chr(num + self.acrii_0) def mult(self, num1, num2, carry): num1 = self.chr_to_int(num1) num2 = self.chr_to_int(num2) carry = self.chr_to_int(carry) result = num1 * num2 + carry carry = 0 if result >= 10 : carry = result // 10 result = result % 10 return self.int_to_chr(result), self.int_to_chr(carry) def add(self, num1, num2): num1 = self.chr_to_int(num1) num2 = self.chr_to_int(num2) result = num1+num2 return self.int_to_chr(result) def multiply(self, num1, num2): if num1 == "0" or num2 == "0": return "0" len_num1 = len(num1) len_num2 = len(num2) answer = [''] * (len_num1 + len_num2) num1 = num1[::-1] num2 = num2[::-1] for j in range(len_num2): for i in range(len_num1): n1 = num1[i] n2 = num2[j] carry = '0' if answer[i+j] == "" else answer[i+j] result, carry = self.mult(n1,n2,carry) answer[i+j] = result if carry != "0" : if answer[i+j+1] != "" : answer[i+j+1] = self.add(answer[i+j+1] ,carry) else: answer[i+j+1] = carry answer = answer[::-1] return "".join(answer) 

### 作弊…

 123 class Solution: def multiply(self, num1, num2): return str(int(num1)*int(num2))