累加数 | 徐年の博客

力扣 306. 累加数

题目说明

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

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

给你一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

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

提示：

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

示例

示例 1:

1
2
3

输入："112358"
输出：true 
解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2:

1
2
3

输入："199100199"
输出：true 
解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题考察的其实就是深度优先搜索的能力和剪枝的判断，让我们来看看具体如何实现的吧。

实现

import java.math.BigInteger;

class Solution {
    /**
     * dfs
     * 大数字
     */
    public boolean isAdditiveNumber(String num) {
        int size = num.length();

        // 第一个数的位数
        int firstSize = 1;

        // 最起码有三个数
        while (firstSize < size - 1) {
            String first = num.substring(0, firstSize);
            if (judge(first)) {
                break;
            }

            // 用BigInteger防止数字过长
            BigInteger firstNum = new BigInteger(first);

            // 遍历第二个数可能的位数
            for (int i = 1; i <= (size - firstSize) / 2; i++) {
                String second = num.substring(firstSize, firstSize + i);
                if (judge(second)) {
                    continue;
                }

                BigInteger secondNum = new BigInteger(second);

                // 深度遍历后序是否符合题意
                if (dfs(num.substring(firstSize + i, size), firstNum, secondNum, 2)) {
                    return true;
                }
            }

            // 第一个数的预设长度加一
            firstSize++;
        }

        // 没找到
        return false;
    }

    /**
     * 判断当前数是否含有前置 0 且不为 0
     */
    public boolean judge(String num) {
        return num.length() > 1 && num.charAt(0) == '0';
    }

    /**
     * 深度遍历
     *
     * @param num       字符串
     * @param firstNum  第一次num
     * @param secondNum 第二个num
     * @param count     已经有几个符合要求的数
     * @return boolean
     */
    public boolean dfs (String num, BigInteger firstNum, BigInteger secondNum, int count) {

        int size = num.length();

        // 当字符串遍历结束且已经有三个以上符合要求的数
        if (size == 0 && count >= 3) {
            return true;
        }

        // 取相加数中 位数更长的作为标记
        int bigSize = Math.max(firstNum.toString().length(), secondNum.toString().length());

        // 剩下的字符串长度不够则匹配失败
        if (size < bigSize) {
            return false;
        }

        // a + b = c, c 可能的位数为 a, b 中较大的位数或加一
        int length = Math.min(size, bigSize + 1);

        for (int i = bigSize; i <= length; i++) {
            String third = num.substring(0, i);
            if (judge(third)) {
                continue;
            }

            BigInteger thirdNum = new BigInteger(third);

            // a + b = c 时继续遍历剩下的字符串
            if (firstNum.add(secondNum).equals(thirdNum)) {
                return dfs(num.substring(i, size), secondNum, thirdNum, count + 1);
            }
            
        }

        return false;
    }
}