Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits '0'-'9', write a function to determine if it’s an additive number.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example 1:
Input: "112358" Output: true Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Example 2:
Input: "199100199" Output: true Explanation: The additive sequence is: 1, 99, 100, 199. 1 + 99 = 100, 99 + 100 = 199
Constraints:
numconsists only of digits'0'-'9'.1 <= num.length <= 35
Solution: DFS
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
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 |
using SV = std::string_view; class Solution { public: bool isAdditiveNumber(SV s) { auto add = [](SV s1, SV s2) { const int l1 = s1.length(), l2 = s2.length(); string s3(max(l1, l2) + 1, '0'); for (int i = 0; i < s3.size() - 1; ++i) { int n1 = i < l1 ? s1[l1 - i - 1] - '0' : 0; int n2 = i < l2 ? s2[l2 - i - 1] - '0' : 0; s3[i] += n1 + n2; if (s3[i] > '9') { s3[i] -= 10; ++s3[i + 1]; } } while (s3.back() == '0' && s3.length() > 1) s3.pop_back(); return string{rbegin(s3), rend(s3)}; }; auto isValid = [](SV s) { return s.length() == 1 || s[0] != '0'; }; function<bool(SV, SV, SV)> additive = [&](SV s1, SV s2, SV right) { if (!isValid(s1) || !isValid(s2)) return false; string s3 = add(s1, s2); const int l3 = s3.length(); if (right.substr(0, l3) != s3) return false; if (right.length() == l3) return true; return additive(s2, s3, right.substr(l3)); }; for (int i = 1; i <= s.size(); ++i) for (int j = 1; i + j <= s.size(); ++j) if (additive(s.substr(0, i), s.substr(i, j), s.substr(i + j))) return true; return false; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution: def isAdditiveNumber(self, num: str) -> bool: n = len(num) def valid(s): return len(s) == 1 or s[0] != '0' def additive(s1, s2, right): if not valid(s1) or not valid(s2): return False s3 = str(int(s1) + int(s2)) if right.startswith(s3): if right == s3: return True return additive(s2, s3, right[len(s3):]) return False for l1 in range(1, n // 2 + 1): for l2 in range(1, n + 1 - l1): if additive(num[:l1], num[l1:l1+l2], num[l1+l2:]): return True return False |