LeetCode 306: Additive Number (String Addition + Split Enumeration)
LeetCode 306StringBacktrackingToday we solve LeetCode 306 - Additive Number.
Source: https://leetcode.com/problems/additive-number/
English
Problem Summary
Given a numeric string num, determine whether it can form an additive sequence. In an additive sequence, each number is the sum of the previous two, and the sequence contains at least three numbers.
Key Insight
Try all valid splits for the first two numbers, then repeatedly compute their sum as a string and check whether the remaining suffix starts with it. Use string addition to avoid overflow.
Algorithm
1) Enumerate first cut i and second cut j.
2) Reject any number with leading zero (unless the number is exactly "0").
3) Simulate sequence by string sum matching.
4) If exactly consumed all characters with at least one successful extension, return true.
Complexity Analysis
Time: O(n^3) in worst case (split enumeration + linear checks).
Space: O(n) for temporary strings.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i < n - 1; i++) {
if (num.charAt(0) == '0' && i > 1) break;
for (int j = i + 1; j < n; j++) {
if (num.charAt(i) == '0' && j - i > 1) break;
if (valid(num, 0, i, j)) return true;
}
}
return false;
}
private boolean valid(String s, int l, int m, int r) {
String a = s.substring(l, m), b = s.substring(m, r);
int idx = r;
boolean used = false;
while (idx < s.length()) {
String c = add(a, b);
if (!s.startsWith(c, idx)) return false;
idx += c.length();
a = b; b = c;
used = true;
}
return idx == s.length() && used;
}
private String add(String x, String y) {
StringBuilder sb = new StringBuilder();
int i = x.length() - 1, j = y.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += x.charAt(i--) - '0';
if (j >= 0) sum += y.charAt(j--) - '0';
sb.append(sum % 10);
carry = sum / 10;
}
return sb.reverse().toString();
}
}func isAdditiveNumber(num string) bool {
n := len(num)
for i := 1; i < n-1; i++ {
if num[0] == '0' && i > 1 {
break
}
for j := i + 1; j < n; j++ {
if num[i] == '0' && j-i > 1 {
break
}
if valid(num, 0, i, j) {
return true
}
}
}
return false
}
func valid(s string, l, m, r int) bool {
a, b := s[l:m], s[m:r]
idx, used := r, false
for idx < len(s) {
c := add(a, b)
if idx+len(c) > len(s) || s[idx:idx+len(c)] != c {
return false
}
idx += len(c)
a, b = b, c
used = true
}
return idx == len(s) && used
}
func add(x, y string) string {
i, j, carry := len(x)-1, len(y)-1, 0
out := make([]byte, 0, max(len(x), len(y))+1)
for i >= 0 || j >= 0 || carry > 0 {
sum := carry
if i >= 0 { sum += int(x[i]-'0'); i-- }
if j >= 0 { sum += int(y[j]-'0'); j-- }
out = append(out, byte(sum%10)+'0')
carry = sum / 10
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return string(out)
}
func max(a, b int) int {
if a > b { return a }
return b
}class Solution {
public:
bool isAdditiveNumber(string num) {
int n = (int)num.size();
for (int i = 1; i < n - 1; i++) {
if (num[0] == '0' && i > 1) break;
for (int j = i + 1; j < n; j++) {
if (num[i] == '0' && j - i > 1) break;
if (valid(num, 0, i, j)) return true;
}
}
return false;
}
bool valid(const string& s, int l, int m, int r) {
string a = s.substr(l, m - l), b = s.substr(m, r - m);
int idx = r;
bool used = false;
while (idx < (int)s.size()) {
string c = add(a, b);
if (idx + (int)c.size() > (int)s.size() || s.substr(idx, c.size()) != c) return false;
idx += (int)c.size();
a = b; b = c;
used = true;
}
return idx == (int)s.size() && used;
}
string add(const string& x, const string& y) {
int i = (int)x.size() - 1, j = (int)y.size() - 1, carry = 0;
string out;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += x[i--] - '0';
if (j >= 0) sum += y[j--] - '0';
out.push_back(char('0' + (sum % 10)));
carry = sum / 10;
}
reverse(out.begin(), out.end());
return out;
}
};class Solution:
def isAdditiveNumber(self, num: str) -> bool:
n = len(num)
for i in range(1, n - 1):
if num[0] == '0' and i > 1:
break
for j in range(i + 1, n):
if num[i] == '0' and j - i > 1:
break
if self._valid(num, 0, i, j):
return True
return False
def _valid(self, s: str, l: int, m: int, r: int) -> bool:
a, b = s[l:m], s[m:r]
idx = r
used = False
while idx < len(s):
c = self._add(a, b)
if not s.startswith(c, idx):
return False
idx += len(c)
a, b = b, c
used = True
return idx == len(s) and used
def _add(self, x: str, y: str) -> str:
i, j, carry = len(x) - 1, len(y) - 1, 0
out = []
while i >= 0 or j >= 0 or carry:
s = carry
if i >= 0:
s += ord(x[i]) - 48
i -= 1
if j >= 0:
s += ord(y[j]) - 48
j -= 1
out.append(chr(48 + s % 10))
carry = s // 10
return ''.join(reversed(out))var isAdditiveNumber = function(num) {
const n = num.length;
for (let i = 1; i < n - 1; i++) {
if (num[0] === '0' && i > 1) break;
for (let j = i + 1; j < n; j++) {
if (num[i] === '0' && j - i > 1) break;
if (valid(num, 0, i, j)) return true;
}
}
return false;
};
function valid(s, l, m, r) {
let a = s.slice(l, m), b = s.slice(m, r);
let idx = r, used = false;
while (idx < s.length) {
const c = add(a, b);
if (!s.startsWith(c, idx)) return false;
idx += c.length;
a = b;
b = c;
used = true;
}
return idx === s.length && used;
}
function add(x, y) {
let i = x.length - 1, j = y.length - 1, carry = 0;
const out = [];
while (i >= 0 || j >= 0 || carry > 0) {
let sum = carry;
if (i >= 0) sum += x.charCodeAt(i--) - 48;
if (j >= 0) sum += y.charCodeAt(j--) - 48;
out.push(String.fromCharCode(48 + (sum % 10)));
carry = Math.floor(sum / 10);
}
return out.reverse().join('');
}中文
题目概述
给定一个数字字符串 num，判断它是否能构成“累加数列”：从第三个数开始，每个数都等于前两个数之和，且序列至少包含三个数。
核心思路
先枚举前两个数的切分位置，然后不断做“字符串加法”得到下一个数，并检查后续子串是否以该和开头。使用字符串加法可以避免整型溢出。
算法步骤
1）枚举第一刀 i 与第二刀 j。
2）处理前导零，除了单独 "0" 外都非法。
3）循环计算和并匹配后缀。
4）若完整消费字符串且至少匹配出一个后续数，则返回 true。
复杂度分析
时间复杂度：O(n^3)。
空间复杂度：O(n)（临时字符串）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public boolean isAdditiveNumber(String num) {
int n = num.length();
for (int i = 1; i < n - 1; i++) {
if (num.charAt(0) == '0' && i > 1) break;
for (int j = i + 1; j < n; j++) {
if (num.charAt(i) == '0' && j - i > 1) break;
if (valid(num, 0, i, j)) return true;
}
}
return false;
}
private boolean valid(String s, int l, int m, int r) {
String a = s.substring(l, m), b = s.substring(m, r);
int idx = r;
boolean used = false;
while (idx < s.length()) {
String c = add(a, b);
if (!s.startsWith(c, idx)) return false;
idx += c.length();
a = b; b = c;
used = true;
}
return idx == s.length() && used;
}
private String add(String x, String y) {
StringBuilder sb = new StringBuilder();
int i = x.length() - 1, j = y.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += x.charAt(i--) - '0';
if (j >= 0) sum += y.charAt(j--) - '0';
sb.append(sum % 10);
carry = sum / 10;
}
return sb.reverse().toString();
}
}func isAdditiveNumber(num string) bool {
n := len(num)
for i := 1; i < n-1; i++ {
if num[0] == '0' && i > 1 {
break
}
for j := i + 1; j < n; j++ {
if num[i] == '0' && j-i > 1 {
break
}
if valid(num, 0, i, j) {
return true
}
}
}
return false
}
func valid(s string, l, m, r int) bool {
a, b := s[l:m], s[m:r]
idx, used := r, false
for idx < len(s) {
c := add(a, b)
if idx+len(c) > len(s) || s[idx:idx+len(c)] != c {
return false
}
idx += len(c)
a, b = b, c
used = true
}
return idx == len(s) && used
}
func add(x, y string) string {
i, j, carry := len(x)-1, len(y)-1, 0
out := make([]byte, 0, max(len(x), len(y))+1)
for i >= 0 || j >= 0 || carry > 0 {
sum := carry
if i >= 0 { sum += int(x[i]-'0'); i-- }
if j >= 0 { sum += int(y[j]-'0'); j-- }
out = append(out, byte(sum%10)+'0')
carry = sum / 10
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return string(out)
}
func max(a, b int) int {
if a > b { return a }
return b
}class Solution {
public:
bool isAdditiveNumber(string num) {
int n = (int)num.size();
for (int i = 1; i < n - 1; i++) {
if (num[0] == '0' && i > 1) break;
for (int j = i + 1; j < n; j++) {
if (num[i] == '0' && j - i > 1) break;
if (valid(num, 0, i, j)) return true;
}
}
return false;
}
bool valid(const string& s, int l, int m, int r) {
string a = s.substr(l, m - l), b = s.substr(m, r - m);
int idx = r;
bool used = false;
while (idx < (int)s.size()) {
string c = add(a, b);
if (idx + (int)c.size() > (int)s.size() || s.substr(idx, c.size()) != c) return false;
idx += (int)c.size();
a = b; b = c;
used = true;
}
return idx == (int)s.size() && used;
}
string add(const string& x, const string& y) {
int i = (int)x.size() - 1, j = (int)y.size() - 1, carry = 0;
string out;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += x[i--] - '0';
if (j >= 0) sum += y[j--] - '0';
out.push_back(char('0' + (sum % 10)));
carry = sum / 10;
}
reverse(out.begin(), out.end());
return out;
}
};class Solution:
def isAdditiveNumber(self, num: str) -> bool:
n = len(num)
for i in range(1, n - 1):
if num[0] == '0' and i > 1:
break
for j in range(i + 1, n):
if num[i] == '0' and j - i > 1:
break
if self._valid(num, 0, i, j):
return True
return False
def _valid(self, s: str, l: int, m: int, r: int) -> bool:
a, b = s[l:m], s[m:r]
idx = r
used = False
while idx < len(s):
c = self._add(a, b)
if not s.startswith(c, idx):
return False
idx += len(c)
a, b = b, c
used = True
return idx == len(s) and used
def _add(self, x: str, y: str) -> str:
i, j, carry = len(x) - 1, len(y) - 1, 0
out = []
while i >= 0 or j >= 0 or carry:
s = carry
if i >= 0:
s += ord(x[i]) - 48
i -= 1
if j >= 0:
s += ord(y[j]) - 48
j -= 1
out.append(chr(48 + s % 10))
carry = s // 10
return ''.join(reversed(out))var isAdditiveNumber = function(num) {
const n = num.length;
for (let i = 1; i < n - 1; i++) {
if (num[0] === '0' && i > 1) break;
for (let j = i + 1; j < n; j++) {
if (num[i] === '0' && j - i > 1) break;
if (valid(num, 0, i, j)) return true;
}
}
return false;
};
function valid(s, l, m, r) {
let a = s.slice(l, m), b = s.slice(m, r);
let idx = r, used = false;
while (idx < s.length) {
const c = add(a, b);
if (!s.startsWith(c, idx)) return false;
idx += c.length;
a = b;
b = c;
used = true;
}
return idx === s.length && used;
}
function add(x, y) {
let i = x.length - 1, j = y.length - 1, carry = 0;
const out = [];
while (i >= 0 || j >= 0 || carry > 0) {
let sum = carry;
if (i >= 0) sum += x.charCodeAt(i--) - 48;
if (j >= 0) sum += y.charCodeAt(j--) - 48;
out.push(String.fromCharCode(48 + (sum % 10)));
carry = Math.floor(sum / 10);
}
return out.reverse().join('');
}
Comments