0306. Additive Number (M)

佚名 5年前 (2020-07-07) 算法 1031人围观抢沙发百度已收录

Additive Number (M)

题目

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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:

num consists only of digits '0'-'9'.
1 <= num.length <= 35

Follow up:
How would you handle overflow for very large input integers?

题意

给定一个字符串，判断能否将该字符串切割成若干个数字，且每个数字都是前两个数字之和。

思路

先确定好最开始的两个数，再递归判断整个字符串。

代码实现

Java

class Solution {
    public boolean isAdditiveNumber(String num) {
        for (int i = 1; i <= num.length() / 2; i++) {
            if (i > 1 && num.charAt(0) == '0') break;
            for (int j = 1; j <= num.length() / 2 && i + j < num.length(); j++) {
                if (j > 1 && num.charAt(i) == '0') break;
                String num1 = num.substring(0, i), num2 = num.substring(i, i + j);
                if (dfs(num.substring(i + j), add(num1, num2), num2)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(String s, String target, String pre) {
        if (s.isEmpty()) {
            return true;
        }

        if (!s.startsWith(target)) {
            return false;
        }

        return dfs(s.substring(target.length()), add(target, pre), target);
    }

    private String add(String s, String t) {
        String sum = "";
        int i = 1;
        int carry = 0;
        while (i <= s.length() || i <= t.length()) {
            int num1 = 0, num2 = 0;
            if (i <= s.length()) {
                num1 = s.charAt(s.length() - i) - '0';
            }
            if (i <= t.length()) {
                num2 = t.charAt(t.length() - i) - '0';
            }
            int tmp = num1 + num2 + carry;
            carry = tmp / 10;
            sum = tmp % 10 + sum;
            i++;
        }
        if (carry != 0) {
            sum = carry + sum;
        }
        return sum;
    }
}