字符串中等1 种解法

#43字符串相乘

不使用大整数类型，也不把完整输入转换为整数，返回两个非负整数字符串的乘积。

#数学#字符串#模拟

解题主线

num1[i] × num2[j] 的个位累加到 result[i+j+1]，进位累加到 result[i+j]。

长度为 m、n 的乘积最多占 m+n 位。

解法 1：竖式乘法数组

逐对相乘并在固定位置完成累加和进位，最后跳过结果的前导零。

时间复杂度

O(mn)

空间复杂度

O(m + n)

43. 字符串相乘 · 竖式乘法数组

java

final class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        int[] digits = new int[num1.length() + num2.length()];
        for (int i = num1.length() - 1; i >= 0; i--) {
            int first = num1.charAt(i) - '0';
            for (int j = num2.length() - 1; j >= 0; j--) {
                int second = num2.charAt(j) - '0';
                int sum = digits[i + j + 1] + first * second;
                digits[i + j + 1] = sum % 10;
                digits[i + j] += sum / 10;
            }
        }
        StringBuilder result = new StringBuilder(digits.length);
        int index = digits[0] == 0 ? 1 : 0;
        while (index < digits.length) result.append(digits[index++]);
        return result.toString();
    }
}

逐对相乘并在固定位置完成累加和进位，最后跳过结果的前导零。

明确排除旧文件中会发生 int 溢出的 atoi 后直接相乘方案。

边界与易错点

旧 multiply1 先调用 atoi 再做 int 乘法，会截断或溢出，不能通过题目大数用例，因此不作为推荐解法。
结果数组最高位可能为 0，构造字符串时只跳过前导零，不能丢掉乘积 0。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

medium/Q043_AtioII_multiply.java