43.字符串相乘

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1：

输入：num1 = “2”, num2 = “3”
输出：”6”

示例 2：

输入：num1 = “123”, num2 = “456”
输出：”56088”

提示：

• 1 <= num1.length, num2.length <= 200
• num1 和 num2 只能由数字组成
• num1 和 num2 都不包含任何前导零，除了数字 0 本身

解析

模拟竖式乘法：num1[i] * num2[j] 的结果对应结果数组的 [i+j, i+j+1] 位置。

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
  if (num1 === "0" || num2 === "0") return "0";

  const m = num1.length;
  const n = num2.length;
  const result = new Array(m + n).fill(0);

  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      const mul = (num1[i] - "0") * (num2[j] - "0");
      const p1 = i + j;
      const p2 = i + j + 1;
      const sum = mul + result[p2];

      result[p2] = sum % 10;
      result[p1] += Math.floor(sum / 10);
    }
  }

  // 去掉前导零
  let str = result.join("");
  while (str[0] === "0") str = str.slice(1);
  return str || "0";
};

竖式乘法的关键观察：num1 的第 i 位与 num2 的第 j 位相乘，结果恰好落在 result[i+j] 和 result[i+j+1] 这两个位置上。时间复杂度 O(mn)。