Leetcode 43. Multiply Strings

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Multiply Strings

2. Solution

解析:Version 1,直接按照学习的乘法计算方式来求解,先计算第二个数的每一位(从个位开始)乘以第一个数,再将得出的结果加到一起。Version 2采用另一种方式实现。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return '0'
result = []
carry = 0
num1 = list(map(int, num1))
num2 = list(map(int, num2))
for i in range(len(num2) -1, -1, -1):
if num2[i] == 0:
continue
temp = self.mul(num1, num2[i], len(num2) - i - 1)
result = self.add(result, temp)
p = [str(num) for num in result]
return ''.join(p)[::-1]


def mul(self, num1, b, index):
result = []
carry = 0
for a in reversed(num1):
product = a * b + carry
result.append(product % 10)
carry = product // 10
if carry > 0:
result.append(carry)
return [0] * index + result


def add(self, a, b):
carry = 0
for i in range(len(b)):
if i < len(a):
x = a[i]
else:
x = 0
y = b[i]
sum = x + y + carry
b[i] = sum % 10
carry = sum // 10
if carry > 0:
b.append(carry)
return b
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return '0'
num1 = list(map(int, num1))
num2 = list(map(int, num2))
m = len(num1)
n = len(num2)
result = [0] * (m + n)
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
product = num1[i] * num2[j]
sum = product + result[i+j+1]
result[i+j+1] = sum % 10
result[i+j] += sum // 10
result = list(map(str, result))
result = ''.join(result).lstrip('0')
return result

Reference

  1. https://leetcode.com/problems/multiply-strings//
如果有收获,可以请我喝杯咖啡!