43. Multiply Strings

Leetcode link

题目简介

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */

题目给我们两个用字符串表示的数字 num1 与 num2

要求我们在不用 bigInt 或者将其整个转换为数字的情况下求出他们的乘积

解题思路

直接模拟乘法的算法，用两个循环来计算乘积

Javascript

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function (num1, num2) {
    if (num1 === '0' || num2 === '0') {
        return '0'
    }
    const len1 = num1.length
    const len2 = num2.length
    const arr = Array(len1 + len2).fill(0)

    for (let i = len1 - 1; i >= 0; i--) {
        for (let j = len2 - 1; j >= 0; j--) {
            let product = (num1[i] - '0') * (num2[j] - '0')
            const sum = product + arr[i + j + 1]
            arr[i + j + 1] = sum % 10
            arr[i + j] += Math.floor(sum / 10)
        }
    }
    const res = arr.join('').replace(/^0+/, '')
    return res === '' ? '0' : res
};

复杂度分析

m 代表 num1 的长度，n 代表 num2 的长度

时间

O(mn)

空间

O(m+n)