43. Multiply Strings 字符串相乘

@TOC

# 题目描述

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

Example 1:

``````Input: num1 = "2", num2 = "3"
Output: "6"
``````

Example 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.

# 解题方法

``````class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
return str(int(num1) * int(num2))
``````

``````class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
if num1 == '0' or num2 == '0':
return '0'
ans = 0
for i, n1 in enumerate(num2[::-1]):
pre = 0
curr = 0
for j, n2 in enumerate(num1[::-1]):
multi = (ord(n1) - ord('0')) * (ord(n2) - ord('0'))
first, second = multi // 10, multi % 10
curr += (second + pre) * (10 ** j)
pre = first
curr += pre * (10 ** len(num1))
ans += curr * (10 ** i)
return str(ans)
``````

C++代码如下：

``````class Solution {
public:
string multiply(string num1, string num2) {
const int M = num1.size();
const int N = num2.size();
const int k = M + N - 2;
vector<int> res(M + N, 0);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
res[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
}
}
int carry = 0;
for (int i = 0; i < res.size(); ++i) {
res[i] += carry;
carry = res[i] / 10;
res[i] %= 10;
}
int start = res.size() - 1;
while (start >= 0 && res[start] == 0)
--start;
if (start < 0) return "0";
string ans;
while (start >= 0) {
ans += char(res[start] + '0');
--start;
}
return ans;
}
};
``````

# 日期

2018 年 6 月 13 日 —— 腾讯赛圆满结束！两个月修得正果哈哈～～ 2019 年 3 月 3 日 —— 3月开始，春天到了