LeetCode 43. 字符串相乘

Categories:

Tags:

题目描述
思路分析
1. 解法一：竖式乘法 + 位置数组（推荐）
相似题目

题目描述

✅ 43. 字符串相乘

思路分析

解法一：竖式乘法 + 位置数组（推荐）

核心思路：

模拟手写竖式乘法，利用位置关系直接将每次单位相乘的结果累加到结果数组对应位置：

关键推导：num1[i] 与 num2[j] 相乘，结果影响 res[i+j]（进位）和 res[i+j+1]（当前位）。

设 m = len(num1)，n = len(num2)，乘积最多 m+n 位：
num1[i] × num2[j] → 积存入 res[i+j+1]
                  → 进位加到 res[i+j]
逆序遍历两个字符串，双重循环完成所有单位乘法，最后跳过前导零拼接结果。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为两字符串长度，双重循环

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

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] res = new int[m + n];
        // 从右到左遍历，模拟竖式乘法
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = mul + res[i + j + 1];
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int digit : res) {
            // 跳过前导零
            if (sb.length() == 0 && digit == 0) {
                continue;
            }
            sb.append(digit);
        }
        return sb.toString();
    }
}

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
		}
	}
	// 跳过前导零并拼接结果
	i := 0
	for i < len(res) && res[i] == 0 {
		i++
	}
	result := ""
	for ; i < len(res); i++ {
		result += string(rune(res[i] + '0'))
	}
	return result
}

相似题目

题目	难度	考察点
415. 字符串相加	简单	大数加法模拟
67. 二进制求和	简单	二进制字符串加法
8. 字符串转换整数 (atoi)	中等	字符串数字解析
50. Pow(x, n)	中等	快速幂模拟
66. 加一	简单	数组模拟大数加一
989. 数组形式的整数加法	简单	数组模拟大数加法

本文作者: HGNULB

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