LC 306. 累加数

题目描述

这是 LeetCode 上的 306. 累加数 ，难度为 中等。

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。

如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1：

1
2
3
4
5
输入："112358"

输出：true 

解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2：
1
2
3
4
5
输入："199100199"

输出：true 

解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

提示：

  • $1 <= num.length <= 35$
  • num 仅由数字（0 - 9）组成

进阶：你计划如何处理由过大的整数输入导致的溢出?

回溯 + 高精度加法

给定的 $nums$ 的长度只有 $35$，且要求序列的第三个数开始由前两个数相加而来。

容易想到通过 DFS 爆搜每个数的分割点，同时利用累加数的特性（第三个数起，每个数均由为前两数之和）进行剪枝。

具体的，我们可以实现一个 boolean dfs(int u) 函数，入参为当前决策到 $num$ 的哪一位，返回值为决策结果（序列）是否为累加数序列，爆搜过程中的分割数序列存放到 $list$ 中。

由于是 从位置 $u$ 作为开始位置决策如何分割出当前数 $x$，我们可以枚举当前数的结束位置，范围为 $[u, n - 1]$，但需要注意分割数不能包含前导零，即如果 $num[u] = 0$，则当前数只能为 $0$。

同时，一个合法的分割数必然满足「其值大小为前两数之和」，因此当前数 $x$ 能够被添加到 $list$ 的充要条件为：

  1. $list$ 长度不足 $2$，即 $x$ 为序列中的前两数，不存在值大小的约束问题，$x$ 可以被直接到 $list$ 并继续爆搜；
  2. $list$ 长度大于等于 $2$，即 $x$ 需要满足「其值大小为前两数之和」要求，以此条件作为剪枝，满足要求的 $x$ 才能追加到 $list$ 中并继续爆搜。

最后，在整个 DFS 过程中我们需要监测「当前数」与「前两数之和」是否相等，而分割数长度最大为 $35$，存在溢出风险，我们需要实现「高精度加法」，实现一个 check 函数，用于检查 a + b 是否为 c，其中 a、b 和 c 均为使用「逆序」存储数值的数组（最高位对应个位，举个 🌰，$a = 35$，则有 [5, 3]）。

若爆搜过程能顺利结束（得到长度至少为 $3$ 的序列），则说明能够拆分出累加数序列，返回 True，否则返回 False。

至此，我们解决了本题，并通过引入「高精度」来回答了「进阶」部分的问题。

Java 代码：

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
class Solution {
    String num;
    int n;
    List<List<Integer>> list = new ArrayList<>();
    public boolean isAdditiveNumber(String _num) {
        num = _num;
        n = num.length();
        return dfs(0);
    }
    boolean dfs(int u) {
        int m = list.size();
        if (u == n) return m >= 3;
        int max = num.charAt(u) == '0' ? u + 1 : n;
        List<Integer> cur = new ArrayList<>();
        for (int i = u; i < max; i++) {
            cur.add(0, num.charAt(i) - '0');
            if (m < 2 || check(list.get(m - 2), list.get(m - 1), cur)) {
                list.add(cur);
                if (dfs(i + 1)) return true;
                list.remove(list.size() - 1);
            }
        }
        return false;
    }
    boolean check(List<Integer> a, List<Integer> b, List<Integer> c) {
        List<Integer> ans = new ArrayList<>();
        int t = 0;
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            if (i < a.size()) t += a.get(i);
            if (i < b.size()) t += b.get(i);
            ans.add(t % 10);
            t /= 10;
        }
        if (t > 0) ans.add(t);
        boolean ok = c.size() == ans.size();
        for (int i = 0; i < c.size() && ok; i++) {
            if (c.get(i) != ans.get(i)) ok = false;
        }
        return ok;
    }
}

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
39
40
41
class Solution {
public:
    string num;
    int n;
    vector<vector<int>> list;
    bool isAdditiveNumber(string _num) {
        num = _num;
        n = num.size();
        return dfs(0);
    }
    bool dfs(int u) {
        int m = list.size();
        if (u == n) return m >= 3;
        int maxv = (num[u] == '0') ? u + 1 : n;
        vector<int> cur;
        for (int i = u; i < maxv; i++) {
            cur.insert(cur.begin(), num[i] - '0');
            if (m < 2 || check(list[m-2], list[m-1], cur)) {
                list.push_back(cur);
                if (dfs(i + 1)) return true;
                list.pop_back();
            }
        }
        return false;
    }
    bool check(vector<int>& a, vector<int>& b, vector<int>& c) {
        vector<int> ans;
        int t = 0;
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            if (i < a.size()) t += a[i];
            if (i < b.size()) t += b[i];
            ans.push_back(t % 10);
            t /= 10;
        }
        if (t) ans.push_back(t);
        if (ans.size() != c.size()) return false;
        for (int i = 0; i < c.size(); i++)
            if (ans[i] != c[i]) return false;
        return true;
    }
};

Python 代码：
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
class Solution:
    def isAdditiveNumber(self, _num: str) -> bool:
        self.num = _num
        self.n = len(_num)
        self.arr = []
        return self.dfs(0)
    
    def dfs(self, u: int) -> bool:
        m = len(self.arr)
        if u == self.n:
            return m >= 3
        maxv = u + 1 if self.num[u] == '0' else self.n
        for i in range(u, maxv):
            cur = [int(self.num[j]) for j in range(i, u-1, -1)]
            if m < 2 or self.check(self.arr[m-2], self.arr[m-1], cur):
                self.arr.append(cur)
                if self.dfs(i + 1):
                    return True
                self.arr.pop()
        return False
    
    def check(self, a: list[int], b: list[int], c: list[int]) -> bool:
        ans = []
        t = 0
        maxv = max(len(a), len(b))
        for i in range(maxv):
            if i < len(a):
                t += a[i]
            if i < len(b):
                t += b[i]
            ans.append(t % 10)
            t //= 10
        if t > 0:
            ans.append(t)
        return ans == c

  • 时间复杂度：爆搜的复杂度为指数级别，且存在剪枝操作，分析时空复杂度意义不大
  • 空间复杂度：爆搜的复杂度为指数级别，且存在剪枝操作，分析时空复杂度意义不大

最后

这是我们「刷穿 LeetCode」系列文章的第 No.306 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。