Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/306.html

 306	Additive Number

 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.

 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

Algorithm

Let the first digit start with one digit, and the second digit will be searched for higher digits. The first two digits are confirmed, and the third digit is obtained by adding them.

The three arrays are arranged to form a string, which is the same length as the original string if it is less than the original length, then take out the second and third numbers from the previous calculation, and use the same method to get the third number, then add the current string, and then sum Compared to the original string length.

Code

Java

  • import java.util.ArrayList;
    
    public class Additive_Number {
    
        public static void main(String[] args) {
            Additive_Number out = new Additive_Number();
            Solution s = out.new Solution();
    
            System.out.println(s.isAdditiveNumber("112358"));
        }
    
    
        // very good follow up analysis
        class Solution {
    
            boolean isFound = false;
    
            public boolean isAdditiveNumber(String num) {
                if (num == null || num.length() == 0) {
                    return false;
                }
    
                dfs(num, 0, new ArrayList<Long>());
    
                return isFound;
            }
    
            private void dfs(String num, int startIndex, ArrayList<Long> out) {
    
                if (isFound) {
                    return;
                }
    
                if (startIndex == num.length()) {
                    // @note: input is [1,2], then should return false
                    // @note: not working if ==3, must be >=3
                    //          input: "112358", out will be "[1, 1, 2, 3, 5, 8]"
                    if (out.size() >= 3) {
                        isFound = true;
                    }
                    return;
                }
    
                for (int i = startIndex; i < num.length(); i++) {
    
                    String current = num.substring(startIndex, i + 1); // @note:+1
    
                    // skip invalid
                    // 检测str的长度大于19就break,因为long的十进制数长度是19位
                    if ((current.length() > 1 && current.charAt(0) == '0') || current.length() > 19) {
                        break; // because all the rest will all start with 0
                    }
    
                    long curNum = Long.valueOf(current);
                    long n = (long) out.size();
    
                    if (out.size() >= 2 && curNum != out.get((int) (n - 1)) + out.get((int) (n - 2))) {
                        continue;
                    }
    
                    out.add(curNum);
                    dfs(num, i + 1, out);
                    out.remove(out.size() - 1);
                }
            }
        }
    }
    
  • Todo
    
  • 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:
        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
    
    ########3
    
    class Solution(object):
      def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        n = len(num)
        for x in range(0, n / 2):
          if x > 0 and num[0] == "0":
            break
          for y in range(x + 1, n):
            if y - x > 1 and num[x + 1] == "0":
              break
            i, j, k = 0, x, y
            while k < n:
              a = int(num[i:j + 1])
              b = int(num[j + 1:k + 1])
              add = str(int(a + b))
              if not num.startswith(add, k + 1):
                break
              if len(add) + 1 + k == len(num):
                return True
              i = j + 1
              j = k
              k = k + len(add)
        return False
    
    

All Problems

All Solutions