Question

306. Additive Number

中文文档

Description

An additive number is a string whose digits can form an 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.

Given a string containing only digits, return true if it is an additive number or false otherwise.

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:

• 1 <= num.length <= 35
• num consists only of digits.

 

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

Solutions

Solution 1

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
}