###### tags: `Leetcode` `medium` `math` `python`

# 43. Multiply Strings

## [題目連結:] https://leetcode.com/problems/multiply-strings/

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

**Note**: You must not use any built-in BigInteger library or convert the inputs to integer directly.

**Example 1:**

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

**Example 2:**

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

## 解題想法:
* 題目要求實作乘法，不能用內建函式

想法:
                    1       2       3
        *           4       5       6
            ____________________________
                    6       12     18
              5     10      15
        4     8     12
tmp:    4     13    28      27     18 

* 因為需要先用最尾數逐一乘
* Step1: 先將num1,num2都反轉
* Step2: 需準備tmp臨時數組，存中間計算過程的值
* Step3: 雙for迴圈兩兩相乘，將結果存入tmp
* Step4: 處理tmp中溢位的位置
* Step5: 最終再將結果reverse (注意反轉後開頭不能是0)

## Python:

class Solution(object):
    def multiply(self, num1, num2):
        res = ''
        #因爲123*456實際你要先用3乘6所以讓字符串倒序
        num1 = num1[::-1]
        num2 = num2[::-1]
        len1 = len(num1)
        len2 = len(num2)
        #臨時數組，需要儲存計算過程中的中間數值
        tmp = [0 for i in range(len1+len2)]
        for i in range(len1):
            for j in range(len2):
                #tmp存每位數的值 再處理溢位 ex: tmp[0+1]=第一位乘第二位+第二位乘第一位
                tmp[i+j] += int(num1[i])*int(num2[j])
        for l in range(len(tmp)):
            #carry溢位 value最終保留
            carry = tmp[l]//10
            value = tmp[l]%10
            #處理進位
            if l+1<len(tmp):
                tmp[l+1]+=carry
            res+=str(value)
        res = res[::-1]
        #去掉前面0(若有ㄉ話)
        #要用while跟len(res)>1 :處理若a*b 有一數為0時狀況
        while res[0]=='0' and len(res)>1:
            res = res[1:]
        return res
        
if __name__ == '__main__':
    result = Solution()
    num1 = "123"
    num2 = "456"
    ans = result.multiply(num1,num2)
    print(ans)
#Input: num1 = "123", num2 = "456"
#Output: "56088"