leetcode

commit ea7e108287fbb30d6445aa397b9414f9fedefc4d
parent dd63796ba7593aa00c2713806779db89a2da630b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  2 Aug 2023 22:57:03 +0200

Random Problem

Diffstat:
A
Problems/0306.cpp
 | 
26
++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 27 insertions(+), 0 deletions(-)
diff --git a/Problems/0306.cpp b/Problems/0306.cpp
@@ -0,0 +1,26 @@
+class Solution {
+public:
+  bool isAdditiveNumber(const string &num) {
+    for (int i = 1; i < num.size(); i++) {
+      long num1 = stol(num.substr(0, i));
+      for (int j = i + 1; j < num.size(); j++) {
+        long n1 = num1, n2 = stol(num.substr(i, j - i)), n3;
+        int next = j;
+        while (next < num.size()) {
+          const string pre = to_string(n3 = n1 + n2);
+
+          auto res =
+              std::mismatch(pre.begin(), pre.end(), num.substr(next).begin());
+          if (res.first != pre.end()) break;
+
+          next += pre.size();
+          n1 = n2, n2 = n3;
+        }
+        if (next == num.size()) return true;
+        if (num[i] == '0') break;
+      }
+      if (num[0] == '0') break;
+    }
+    return false;
+  }
+};
diff --git a/README.md b/README.md
@@ -232,6 +232,7 @@ for solving problems.
 |  0299  |   Medium   | [Bulls and Cows](Problems/0299.cpp)                                                              |
 |  0300  |   Medium   | [Longest Increasing Subsequence](Problems/0300.cpp)                                              |
 |  0304  |   Medium   | [Range Sum Query 2D - Immutable](Problems/0304.cpp)                                              |
+|  0306  |   Medium   | [Additive Number](Problems/0306.cpp)                                                             |
 |  0309  |   Medium   | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp)                               |
 |  0310  |   Medium   | [Minimum Height Trees](Problems/0310.cpp)                                                        |
 |  0319  |   Medium   | [Bulb Switcher](Problems/0319.cpp)                                                               |