0043.字符串相乘

https://leetcode.cn/problems/multiply-strings/

方法一：模拟加法

时间复杂度 $O((m+n) \times n) = O(mn+n^2)$ ，空间复杂度 $O(m+n)$ ，其中 m，n 分别表示 num1，num2的长度。


func multiply(num1, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	ans := ""
	for i := 0; i < len(num2); i++ {
		tmp, a, mod := "", int(num2[i]-'0'), 0
		for j := len(num1) - 1; j >= 0; j-- {
			b := int(num1[j] - '0')
			tmp = fmt.Sprintf("%d", (a*b+mod)%10) + tmp
			mod = (a*b + mod) / 10
		}
		if mod != 0 {
			tmp = fmt.Sprintf("%d", mod) + tmp
		}
		ans = add(ans+"0", tmp)
	}
	return ans
}

func add(num1, num2 string) string {
	ans, mod := "", 0
	for len(num1) > 0 || len(num2) > 0 || mod > 0 {
		a, b := 0, 0
		if len(num1) > 0 {
			a, num1 = int(num1[len(num1)-1]-'0'), num1[:len(num1)-1]
		}
		if len(num2) > 0 {
			b, num2 = int(num2[len(num2)-1]-'0'), num2[:len(num2)-1]
		}
		ans = fmt.Sprintf("%d", (a+b+mod)%10) + ans
		mod = (a + b + mod) / 10
	}
	return ans
}