43. Multiply Strings

LeetCode 43. Multiply Strings****

Description

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 = "123", num2 = "456"
Output: "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.

Tags

Math, String

Solution

If m, n are lengths of two strings respectively, the length of the product of both is either m+n-1 or m+n. Based on this conclusion, we build an int array whose length is m+n to store the interim result. In particular, we add the product of num1[i] and num2[j] to ints[i+j+1], because the carry of the result will be added to ints[i+j]. After multiplication, we process the carries on each bit. Finally, we trim the leading zero and return the result string converted from the array.

Complexity

• Time complexity: $O(mn)$

• Space complexity: $O(m+n)$

Code

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	var ans string
	ints := make([]int, len(num1)+len(num2))
	for i := len(num1) - 1; i >= 0; i-- {
		for j := len(num2) - 1; j >= 0; j-- {
			ints[i+j+1] += int(num1[i]-'0') * int(num2[j]-'0')
		}
	}
	for i := len(ints) - 1; i > 0; i-- {
		ints[i-1] += ints[i] / 10
		ints[i] %= 10
	}
	for _, n := range ints {
		ans += strconv.Itoa(n)
	}
	// trim leading 0
	idx := 0
	for i, c := range ans {
		if c != '0' {
			idx = i
			break
		}
	}
	return ans[idx:]
}

Reference

1. 字符串相乘