企业官网建设流程全解析

LeetCode 43.字符串相乘

题意

给定两个以字符串形式表示的非负整数 num1 和 num2 ，返回 num1 * num2 的字符串结果，不能直接转long/int计算。

核心思路

1. m长度 × n长度，乘积最多 m+n 位；
2. 创建长度 m+n 的数组保存每一位中间乘积；
3. 从后往前逐位相乘，叠加到数组对应位置，最后统一处理进位；
4. 去除前导零，输出结果。

Java完整代码

java

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[] arr = new int[m + n];

// 逆序遍历每一位相乘 for (int i = m - 1; i >= 0; i--) { int a = num1.charAt(i) - '0'; for (int j = n - 1; j >= 0; j--) { int b = num2.charAt(j) - '0'; int sum = a * b + arr[i + j + 1]; arr[i + j + 1] = sum % 10; arr[i + j] += sum / 10; } } //拼接字符串，跳过前导0 StringBuilder sb = new StringBuilder(); for (int x : arr) { if (!(sb.length() == 0 && x == 0)) { sb.append(x); } } return sb.toString(); }

}

算法原理

• i+j+1 ：低位，存放余数； i+j ：高位，存放进位
• 两层循环模拟手工竖式乘法
• 特殊判定：有一个是0直接返回"0"，避免空串

复杂度

• 时间复杂度：O(m\times n)，m、n为两个字符串长度
• 空间复杂度：O(m+n)，结果数组

测试示例

java

public static void main(String[] args) {
Solution sol=new Solution();
System.out.println(sol.multiply(“123”,“456”));
//输出56088
}

如果你需要模拟竖式逐行累加写法（更贴近手写演算），我可以给出另一版实现。