(Medium) LeetCode - Multiply Strings

tags: Go

category: LeetCode

description: LeetCode - Multiply Strings

created_at: 2021/08/09 20:00:00

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

簡介

這題就是很早以前學程式的時候很經典的題目 「大數乘法」，主要核心的話大概就是知道直式的乘法怎麼算，就那個邏輯，不知道的話現在趕快拿起紙跟筆算一次

在數字很大的時候直接用數字運算可能會溢位(overflow)，所以才會用字串存，雖然現在滿多語言都有支援大數的，但在早期還不知道的時候就只能自己開陣列算，就得用到直式乘法的邏輯，算完再把陣列組起來。

下面一樣附上 Go 的程式碼。只是這次難得直接 0ms

func multiply(num1 string, num2 string) string {
    // 如果其中一個數字是0，相乘必為0
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    // 開一個陣列存答案，長度是兩個數字的相加，因為就算是9*9，也是兩位數=81
    num3 := make([]int, len(num1) + len(num2))
    result := ""

    // 開始直式乘法
    for i := 0; i < len(num1); i++ {
        for j := 0; j < len(num2); j++ {
            num3[i+j+1] += int((num1[i]-48) * (num2[j]-48))
        }
    }

    // 乘完一次進位
    for i := len(num3) - 1; i > 0; i-- {
        num3[i-1] += num3[i] / 10
        num3[i] %= 10
    }

    // 把答案組起來
    for i := 0; i < len(num3); i++ {
        result += strconv.Itoa(num3[i])
    }

    // 去掉前綴0
    return strings.TrimLeft(result, "0")
}