forked from shruti170901/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Additive number.cpp
59 lines (49 loc) · 1.68 KB
/
Additive number.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
// PROBLEM LINK: https://leetcode.com/problems/additive-number/submissions/
class Solution {
public:
bool isAdditiveNumber(string num) {
if (num.size() < 3) {
return false;
}
std::string_view str(num);
for (int i = 0; i < num.size() - 2; ++i) {
for (int j = i+1; j < num.size() - 1; ++j) {
if (j > i+1 && num[i+1] == '0') break;
if (isAdditiveSuffix(str.substr(0, i+1), str.substr(i+1, j - i), str.substr(j+1))) return true;
}
}
return false;
}
bool isAdditiveSuffix(string_view first, string_view second, string_view suffix) {
std::string sum_string;
longSumm(first, second, sum_string);
if (suffix.substr(0, sum_string.size()) == sum_string) {
if (suffix.size() == sum_string.size()) return true;
return isAdditiveSuffix(second, sum_string, suffix.substr(sum_string.size()));
}
return false;
}
void longSumm(string_view first, string_view second, std::string& out) {
if (second.size() > first.size()) {
swap(second, first);
}
out = std::string{first};
char c = 0;
for (int i = out.size()-1, j = second.size()-1; i >= 0; --i, --j) {
char d = 0;
if (j >= 0) {
d += (second[j] - '0');
}
d += (out[i] - '0') + c;
out[i] = '0' + (d % 10);
if (d > 9) {
c = 1;
} else {
c = 0;
}
}
if (c > 0) {
out.insert(out.begin(), '0' + c);
}
}
};