動機

這題是考細心，基本上一般人都知道做法， 但是要實作就是細細思考，處理小細節

同時善用function去包常call的操作，降低實作的複雜度，以免在寫出來之前頭腦先爆炸

Problem

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 = 3Output: 6

Example 2:

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

 

Constraints:

  • 1 <= num1.length, num2.length <= 200
  • num1 and num2 consist of digits only.
  • Both num1 and num2 do not contain any leading zero, except the number 0 itself.

Sol

每次都是一個digit去乘被乘數，第一個function

被所有digit乘完後，就是把他們加起來，第二個function

最後把前導的零刪掉

def mulDigit(arr,n):
    # 1 2 3 4 * 5
    carry = 0
    for i in reversed(range(0,len(arr))):
        tmp = arr[i] * n + carry
        carry, arr[i] = [tmp//10, tmp%10]
    if carry > 0:
        return [carry]+arr
    else:
        return arr
def combine(a,b):
    # len(b) >= len(a)
    #    1 2 3 4
    #  1 2 3 4 5
    carry = 0
    j = len(a) - 1
    for i in reversed(range(0,len(b))):
        if j < 0:
            if carry > 0:
                b[i] += carry
                carry = 0
            return b
        else:
            tmp = a[j] + b[i] + carry
            carry, b[i] = [tmp//10, tmp%10]
            j -= 1
    if carry > 0:
        return [carry]+b
    else:
        return b
def delLeadingZero(arr):
    for i in range(0,len(arr)):
        if arr[i] != 0:
            break
    if i < len(arr):
        return arr[i:]
    else:
        return [0]
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        n1 = [int(c) for c in num1]
        n2 = [int(c) for c in num2]
        
        ret = [0]
        i = 0
        for n in reversed(n2):
            #print(n1,n)
            tmp = mulDigit(n1[:],n)
            tmp += [0]*i
            #print(ret,tmp)
            ret = combine(ret, tmp)
            i += 1
        
        return ''.join([str(n) for n in delLeadingZero(ret)])