forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmultiply-strings.cpp
110 lines (96 loc) · 3.11 KB
/
multiply-strings.cpp
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Time: O(m * n)
// Space: O(m + n)
class Solution {
public:
string multiply(string num1, string num2) {
string result(num1.size() + num2.size(), '0');
for (int i = num1.size() - 1; i >= 0; --i) {
for (int j = num2.size() - 1; j >= 0; --j) {
int sum = (num1[i] - '0') * (num2[j] - '0') + (result[i + j + 1] - '0');
result[i + j + 1] = sum % 10 + '0';
result[i + j] += sum / 10;
}
}
int pos = result.find_first_not_of('0');
if (pos != string::npos) {
return result.substr(pos);
}
return "0";
}
};
// Time: O(m * n)
// Space: O(m + n)
class Solution2 {
public:
string multiply(string num1, string num2) {
const auto char_to_int = [](const char c) { return c - '0'; };
const auto int_to_char = [](const int i) { return i + '0'; };
vector<int> n1;
transform(num1.rbegin(), num1.rend(), back_inserter(n1), char_to_int);
vector<int> n2;
transform(num2.rbegin(), num2.rend(), back_inserter(n2), char_to_int);
vector<int> tmp(n1.size() + n2.size());
for(int i = 0; i < n1.size(); ++i) {
for(int j = 0; j < n2.size(); ++j) {
tmp[i + j] += n1[i] * n2[j];
tmp[i + j + 1] += tmp[i + j] / 10;
tmp[i + j] %= 10;
}
}
string res;
transform(find_if(tmp.rbegin(), prev(tmp.rend()),
[](const int i) { return i != 0; }),
tmp.rend(), back_inserter(res), int_to_char);
return res;
}
};
// Time: O(m * n)
// Space: O(m + n)
// Define a new BigInt class solution.
class Solution3 {
public:
string multiply(string num1, string num2) {
return BigInt(num1) * BigInt(num2);
}
class BigInt {
public:
BigInt(const string& s) {
transform(s.rbegin(), s.rend(), back_inserter(n_),
[](const char c) { return c - '0'; });
}
operator string() {
string s;
transform(find_if(n_.rbegin(), prev(n_.rend()),
[](const int i) { return i != 0; }),
n_.rend(), back_inserter(s),
[](const int i) { return i + '0'; });
return s;
}
BigInt operator*(const BigInt &rhs) const {
BigInt res(n_.size() + rhs.size(), 0);
for(auto i = 0; i < n_.size(); ++i) {
for(auto j = 0; j < rhs.size(); ++j) {
res[i + j] += n_[i] * rhs[j];
res[i + j + 1] += res[i + j] / 10;
res[i + j] %= 10;
}
}
return res;
}
private:
vector<int> n_;
BigInt(int num, int val): n_(num, val) {
}
// Getter.
int operator[] (int i) const {
return n_[i];
}
// Setter.
int & operator[] (int i) {
return n_[i];
}
size_t size() const {
return n_.size();
}
};
};