43. Multiply Strings
給定兩個由字符串表示的非負整數 num1 和 num2，返回 num1 和 num2 的乘積，結果也應表示為字符串。
注意：你不能使用任何內置的大數庫或直接將輸入轉換為整數。
範例 1：
輸入：num1 = "2", num2 = "3" 輸出："6"
Python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == "0" or num2 == "0":
return "0"
# Initialize result list
result = [0] * (len(num1) + len(num2))
# Reverse both strings to facilitate multiplication
num1, num2 = num1[::-1], num2[::-1]
# Multiply each digit of num1 with each digit of num2
for i in range(len(num1)):
for j in range(len(num2)):
result[i + j] += int(num1[i]) * int(num2[j])
result[i + j + 1] += result[i + j] // 10
# Carry over to the next digit
result[i + j] %= 10 # Remainder stays in the current position
# Remove leading zeros
while len(result) > 1 and result[-1] == 0:
result.pop()
# Convert result list back to string
result = result[::-1]
return ''.join(map(str, result))
16.35MB, 108ms
C++
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0") {
return "0";
}
int n = num1.size();
int m = num2.size();
vector<int> result(n + m, 0);
// Reverse both strings to facilitate multiplication
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
// Multiply each digit of num1 with each digit of num2
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
result[i + j] += (num1[i] - '0') * (num2[j] - '0');
result[i + j + 1] += result[i + j] / 10; // Carry over to the next
digit
result[i + j] %= 10; // Remainder stays in the current position
}
}
// Remove leading zeros
while (result.size() > 1 && result.back() == 0) {
result.pop_back();
}
// Convert result list back to string
string product;
for (int i = result.size() - 1; i >= 0; --i) {
product.push_back(result[i] + '0');
}
return product;
}
};
8.18MB, 7ms
Javascript
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function(num1, num2) {
if (num1 === "0" || num2 === "0") {
return "0";
}
const n = num1.length;
const m = num2.length;
const result = new Array(n + m).fill(0);
// Reverse both strings to facilitate multiplication
num1 = num1.split('').reverse().join('');
num2 = num2.split('').reverse().join('');
// Multiply each digit of num1 with each digit of num2
for (let i = 0; i < n; ++i) {
for (let j = 0; j < m; ++j) {
result[i + j] += (num1[i] - '0') * (num2[j] - '0');
result[i + j + 1] += Math.floor(result[i + j] / 10);
// Carry over to the next digit
result[i + j] %= 10; // Remainder stays in the current position
}
}
// Remove leading zeros
while (result.length > 1 && result[result.length - 1] === 0) {
result.pop();
}
// Convert result list back to string
return result.reverse().join('');
};
52.48MB, 67ms
