## [Leetcode]43. Multiply Strings(C++)

### 题目描述

Given two non-negative integers `num1` and `num2` represented as strings, return the product of `num1` and `num2`, also represented as a string.

### 例子

#### 例子 1

Input: num1 = “2”, num2 = “3” Output: “6”

#### 例子 2

Input: num1 = “123”, num2 = “456” Output: “56088”

### Note

1. The length of both `num1` and `num2` is < 110.
2. Both `num1` and `num2` contain only digits `0-9`.
3. Both `num1` and `num2` do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

### 解题思路

``````#include <algorithm>
#include <string>
#include <vector>

class Solution {
public:
std::string multiply(std::string num1, std::string num2) {
if (num1 == "0" || num2 == "0") return "0";

std::vector<std::string> prods;
for (int i = num1.length() - 1; i >= 0; i--) {
std::string prod = multiplyOneDigit(num2, num1[i] - '0');
prod += std::string(num1.length() - 1 - i, '0');
prods.push_back(prod);
}

std::string result = prods[0];
for (int i = 1; i < prods.size(); i++) {
}

return result;
}

private:
std::string multiplyOneDigit(const std::string& num, int digit) {
std::string result = "";
int res = 0;
for (int i = num.length() - 1; i >= 0; i--) {
int prod = (num[i] - '0') * digit;
std::string prod_s =
std::to_string(prod) + std::string(num.length() - 1 - i, '0');
}

if (res > 0) {
result += ('0' + res);
}
return result;
}

std::string addTwoInt(const std::string& num1, const std::string& num2) {
std::string result = "";
int ptr1 = num1.length() - 1, ptr2 = num2.length() - 1;
int res = 0;
while (ptr1 >= 0 || ptr2 >= 0) {
int sum = 0;
if (ptr2 >= 0) {
sum += num2[ptr2] - '0';
}
if (ptr1 >= 0) {
sum += num1[ptr1] - '0';
}
sum += res;
res = 0;
if (sum >= 10) {
res = 1;
sum -= 10;
}
ptr1--;
ptr2--;
result += ('0' + sum);
}
if (res > 0) {
result += ('0' + res);
}

std::reverse(result.begin(), result.end());
return result;
}
};
``````
• 时间复杂度: O(mn)
• 空间复杂度: O(mn)

GitHub 代码同步地址： 43.MultiplyStrings.cpp

Built with Hugo
Theme Stack designed by Jimmy