Question

306. 累加数

English Version

题目描述

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

一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

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

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

 

示例 1：

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

示例 2：

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

 

提示：

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

 

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

解法

方法一

class Solution:
  def isAdditiveNumber(self, num: str) -> bool:
    def dfs(a, b, num):
      if not num:
        return True
      if a + b > 0 and num[0] == '0':
        return False
      for i in range(1, len(num) + 1):
        if a + b == int(num[:i]):
          if dfs(b, a + b, num[i:]):
            return True
      return False

    n = len(num)
    for i in range(1, n - 1):
      for j in range(i + 1, n):
        if i > 1 and num[0] == '0':
          break
        if j - i > 1 and num[i] == '0':
          continue
        if dfs(int(num[:i]), int(num[i:j]), num[j:]):
          return True
    return False

class Solution {
  public boolean isAdditiveNumber(String num) {
    int n = num.length();
    for (int i = 1; i < Math.min(n - 1, 19); ++i) {
      for (int j = i + 1; j < Math.min(n, i + 19); ++j) {
        if (i > 1 && num.charAt(0) == '0') {
          break;
        }
        if (j - i > 1 && num.charAt(i) == '0') {
          continue;
        }
        long a = Long.parseLong(num.substring(0, i));
        long b = Long.parseLong(num.substring(i, j));
        if (dfs(a, b, num.substring(j))) {
          return true;
        }
      }
    }
    return false;
  }

  private boolean dfs(long a, long b, String num) {
    if ("".equals(num)) {
      return true;
    }
    if (a + b > 0 && num.charAt(0) == '0') {
      return false;
    }
    for (int i = 1; i < Math.min(num.length() + 1, 19); ++i) {
      if (a + b == Long.parseLong(num.substring(0, i))) {
        if (dfs(b, a + b, num.substring(i))) {
          return true;
        }
      }
    }
    return false;
  }
}

class Solution {
public:
  bool isAdditiveNumber(string num) {
    int n = num.size();
    for (int i = 1; i < min(n - 1, 19); ++i) {
      for (int j = i + 1; j < min(n, i + 19); ++j) {
        if (i > 1 && num[0] == '0') break;
        if (j - i > 1 && num[i] == '0') continue;
        auto a = stoll(num.substr(0, i));
        auto b = stoll(num.substr(i, j - i));
        if (dfs(a, b, num.substr(j, n - j))) return true;
      }
    }
    return false;
  }

  bool dfs(long long a, long long b, string num) {
    if (num == "") return true;
    if (a + b > 0 && num[0] == '0') return false;
    for (int i = 1; i < min((int) num.size() + 1, 19); ++i)
      if (a + b == stoll(num.substr(0, i)))
        if (dfs(b, a + b, num.substr(i, num.size() - i)))
          return true;
    return false;
  }
};

func isAdditiveNumber(num string) bool {
  n := len(num)
  var dfs func(a, b int64, num string) bool
  dfs = func(a, b int64, num string) bool {
    if num == "" {
      return true
    }
    if a+b > 0 && num[0] == '0' {
      return false
    }
    for i := 1; i < min(len(num)+1, 19); i++ {
      c, _ := strconv.ParseInt(num[:i], 10, 64)
      if a+b == c {
        if dfs(b, c, num[i:]) {
          return true
        }
      }
    }
    return false
  }
  for i := 1; i < min(n-1, 19); i++ {
    for j := i + 1; j < min(n, i+19); j++ {
      if i > 1 && num[0] == '0' {
        break
      }
      if j-i > 1 && num[i] == '0' {
        continue
      }
      a, _ := strconv.ParseInt(num[:i], 10, 64)
      b, _ := strconv.ParseInt(num[i:j], 10, 64)
      if dfs(a, b, num[j:]) {
        return true
      }
    }
  }
  return false
}