LeetCode 43. 字符串相乘

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 43. 字符串相乘

思路分析

竖式乘法

参考代码

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	m, n := len(num1), len(num2)
	res := make([]int, m+n)
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			mul := int(num1[i]-'0') * int(num2[j]-'0')
			sum := mul + res[i+j+1]
			res[i+j+1] = sum % 10
			res[i+j] += sum / 10
		}
	}
	var sb strings.Builder
	for _, digit := range res {
		sb.WriteString(fmt.Sprintf("%d", digit))
	}
	return strings.TrimLeft(sb.String(), "0")
}

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}

	n1, n2 := len(num1), len(num2)
	res := make([]int, n1+n2)

	// 从右到左遍历 num1 和 num2
	for i := n1 - 1; i >= 0; i-- {
		for j := n2 - 1; j >= 0; j-- {
			mul := int(num1[i]-'0') * int(num2[j]-'0')
			p1, p2 := i+j, i+j+1
			sum := mul + res[p2]

			res[p2] = sum % 10
			res[p1] += sum / 10
		}
	}

	i := 0
	for i < len(res) && res[i] == 0 {
		i++
	}
	result := ""
	for ; i < len(res); i++ {
		result += string(res[i] + '0')
	}
	return result
}

时间复杂度：O (m * n)，其中 m 和 n 分别是 num1 和 num2 的长度。

空间复杂度：O (m + n)，用于存储乘法结果数组。

➡️ 点击查看 Java 题解(一)

write your code here

➡️ 点击查看 Java 题解(二)

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/15837549