LeetCode 43. 字符串相乘

约 5 分钟
文章信息 22 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 虾皮 图森 携程 哔哩哔哩
标签
字符串 数学 模拟 加法问题
目录

题目描述

✅ 43. 字符串相乘

image-20220916001134670

题意分析

两个非负整数以字符串形式给出，要求返回它们乘积的字符串形式，并且题面明确禁止把输入直接转成整数、也禁止使用处理大整数的内置库。

「以字符串给出且禁止转成整数」是最强的信号：它等于直接告诉你，数字的位数可以远远超过任何内置整型的表示范围，考点就是手工模拟竖式乘法。用 long 会静默溢出得到错误结果，用大整数类型则完全绕开考点，两条路都不能走。

输入的另一个约束是「不含前导零，除非数字本身就是 0」。这条约束让输入侧很干净，但输出侧仍需自己处理前导零：结果数组的最高位有可能是 0，必须跳过后再拼接。

需要留意的边界情形：任一乘数是 "0" 时结果是 "0"，而不是一串零、也不是空串；两个乘数长度差别可能很大，索引公式必须对任意长度组合都成立；结果的位数不是固定的——m 位数乘 n 位数，乘积要么 m + n 位（如 99 × 99 = 9801），要么 m + n - 1 位（如 12 × 34 = 408），所以最多只会出现一个前导零。

解法：数组模拟竖式乘法

核心思路

用长度为 m + n 的数组保存乘积。数位 num1[i] 与 num2[j] 的乘积落在 digits[i + j + 1]，进位累加到 digits[i + j]。

两个下标都从低位向高位遍历，边累加边处理进位；最后跳过前导零并拼接结果。任一乘数为 "0" 时直接返回 "0"。

解题步骤

  • 若任一乘数为 "0"，直接返回 "0"。
  • 创建长度为 m + n 的结果数组。
  • 从右向左枚举两串的每一对数位，将乘积本位写入 i + j + 1，进位累加到 i + j。
  • 跳过结果数组的前导零，将剩余数位拼成字符串。

代码实现

class Solution {
    public String multiply(String num1, String num2) {
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }

        int m = num1.length();
        int n = num2.length();
        int[] digits = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                int pos = i + j + 1;
                int sum = digits[pos] + x * y;

                digits[pos] = sum % 10;
                digits[pos - 1] += sum / 10;
            }
        }

        StringBuilder ans = new StringBuilder();
        int idx = 0;
        while (idx < digits.length && digits[idx] == 0) {
            idx++;
        }
        while (idx < digits.length) {
            ans.append(digits[idx]);
            idx++;
        }

        return ans.toString();
    }
}

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

    m := len(num1)
    n := len(num2)
    digits := make([]int, m+n)

    for i := m - 1; i >= 0; i-- {
        x := int(num1[i] - '0')
        for j := n - 1; j >= 0; j-- {
            y := int(num2[j] - '0')
            pos := i + j + 1
            sum := digits[pos] + x*y

            digits[pos] = sum % 10
            digits[pos-1] += sum / 10
        }
    }

    idx := 0
    for idx < len(digits) && digits[idx] == 0 {
        idx++
    }
    ans := make([]byte, 0, len(digits)-idx)
    for idx < len(digits) {
        ans = append(ans, byte(digits[idx])+'0')
        idx++
    }

    return string(ans)
}

复杂度分析

  • 时间复杂度：$O(mn)$，枚举两串的所有数位组合。
  • 空间复杂度：$O(m + n)$，结果数组最多有 m + n 位。

关键点总结

  • 长度为 m + n 的数组足以容纳乘积和最高位进位。
  • 本位下标是 i + j + 1，进位下标是 i + j。
  • 进位必须累加而非覆盖，输出时要去掉前导零。

易错点总结

  • 结果数组长度应为 m + n，否则最低位会越界。
  • 进位要使用 +=，使用赋值会覆盖之前的进位。
  • 两层循环必须从低位向高位处理，保证进位最终被归一化。
  • 要特判零并跳过非零结果的前导零。

相似题目

题目 难度 考察点
415. 字符串相加 简单 只做加法，落点固定为同一位，进位恒为 0 或 1，是本题的前置基本功
2. 两数相加 中等 载体换成逆序链表，无需下标计算，边遍历边构造结果节点
67. 二进制求和 简单 基数由 10 变 2，验证取余与整除的除数是唯一需要随进制改动的地方
LCR 002. 二进制求和 简单 与 67 同题异名，可用来练「双指针从末尾对齐 + 统一进位」的最短写法
66. 加一 简单 加数固定为 1，绝大多数情况只改末位，仅全为 9 时才需要扩位
989. 数组形式的整数加法 简单 另一个加数是普通整数，可整体塞进进位变量，用一个循环同时消化两侧
1073. 负二进制数相加 中等 基数为 -2，进位可能是 -1，需要向高位「借负」，打破进位非负的直觉