Skip to content

306. Additive Number

  • Time: $O(n^2)$
  • Space: $O(n)$
 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 {
 public:
  bool isAdditiveNumber(string num) {
    const int n = num.length();

    // num[0..i] = firstNum
    for (int i = 0; i < n / 2; ++i) {
      if (i > 0 && num[0] == '0')
        return false;
      const long firstNum = stol(num.substr(0, i + 1));
      // num[i + 1..j] = secondNum
      // |thirdNum| >= max(|firstNum|, |secondNum|)
      for (int j = i + 1; max(i, j - i) < n - j; ++j) {
        if (j > i + 1 && num[i + 1] == '0')
          break;
        const long secondNum = stol(num.substr(i + 1, j - i));
        if (dfs(num, firstNum, secondNum, j + 1))
          return true;
      }
    }

    return false;
  }

 private:
  bool dfs(const string& num, long firstNum, long secondNum, long s) {
    if (s == num.length())
      return true;

    const long thirdNum = firstNum + secondNum;
    const string& thirdNumStr = to_string(thirdNum);
    return num.find(thirdNumStr, s) == s &&
           dfs(num, secondNum, thirdNum, s + thirdNumStr.length());
  }
};

 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
class Solution {
  public boolean isAdditiveNumber(String num) {
    final int n = num.length();

    // num[0..i] = firstNum
    for (int i = 0; i < n / 2; ++i) {
      if (i > 0 && num.charAt(0) == '0')
        return false;
      final long firstNum = Long.parseLong(num.substring(0, i + 1));
      // num[i + 1..j] = secondNum
      // |thirdNum| >= max(|firstNum|, |secondNum|)
      for (int j = i + 1; Math.max(i, j - i) < n - j; ++j) {
        if (j > i + 1 && num.charAt(i + 1) == '0')
          break;
        final long secondNum = Long.parseLong(num.substring(i + 1, j + 1));
        if (dfs(num, firstNum, secondNum, j + 1))
          return true;
      }
    }

    return false;
  }

  private boolean dfs(final String num, long firstNum, long secondNum, long s) {
    if (s == num.length())
      return true;

    final long thirdNum = firstNum + secondNum;
    final String thirdNumStr = String.valueOf(thirdNum);
    return num.indexOf(thirdNumStr, (int) s) == s &&
        dfs(num, secondNum, thirdNum, s + thirdNumStr.length());
  }
}

 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
class Solution:
  def isAdditiveNumber(self, num: str) -> bool:
    n = len(num)

    def dfs(firstNum: int, secondNum: int, s: int) -> bool:
      if s == len(num):
        return True

      thirdNum = firstNum + secondNum
      thirdNumStr = str(thirdNum)

      return (num.find(thirdNumStr, s) == s and
              dfs(secondNum, thirdNum, s + len(thirdNumStr)))

    # num[0..i] = firstNum
    for i in range(n // 2):
      if i > 0 and num[0] == '0':
        return False
      firstNum = int(num[:i + 1])
      # num[i + 1..j] = secondNum
      # |thirdNum| >= max(|firstNum|, |secondNum|)
      j = i + 1
      while max(i, j - i) < n - j:
        if j > i + 1 and num[i + 1] == '0':
          break
        secondNum = int(num[i + 1:j + 1])
        if dfs(firstNum, secondNum, j + 1):
          return True
        j += 1

    return False