• This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together
  • LeetCode: 306
    • Time: 2022-01-10
    • Strength button difficulty: Medium
    • Personal difficulty: Medium+
    • Data structure: string, decision tree
    • Algorithm: DFS, backtracking, high precision addition

2022-01-10: LeetCode: 306

1. Topic description

  • Title: Original title link

    • A cumulative number is a string of numbers that form a cumulative sequence.
    • A valid summation sequence must contain at least three numbers. All but the first two numbers in the string are equal to the sum of their previous two numbers.
    • Given a string containing only the numbers ‘0’-‘9’, write an algorithm to determine if the given input is cumulative. If so, return true; Otherwise, return false.
    • Note: Numbers in the summation sequence do not begin with 0, so 1, 2, 03 or 1, 02, 3 cannot occur.
    • The length of the input sequence satisfies:1 <= num.length <= 35

  • Input output specification

    • Input: string
    • Output: Boolean value indicating whether the string is cumulative

  • Input and output examples

    • Input: “199100199”
    • Output: true,

2. Method 1: Recursion: DFS & String Addition (high-precision addition)

  • Idea: recursive – DFS deep search

    • If the sequence represented by a string is a summation, all numbers except the first two are equal to the sum of the first two numbers
    • Therefore, the overall idea is to determine the value of the third number according to the first two numbers each time, and then take out the number of the same length as the third number in the sequence to match
      • When matched, the starting subscript position corresponding to the value is recordedindex, for the next recursion, continue the next round of cumulative number judgment
      • If not, return false
    • When analyzing whether the sum of the first two numbers equals the third, note that the number of digits is indeterminate and can be one, two, and so on
      • So the outer layer needs a double loop corresponding to the first two numbers, and the loop variables are respectively the ending indices of the first two numbers in the summation sequence
      • The inner layer searches the entire sequence recursively (DFS) to match and find the third number
    • Pay attention to
      • The following sequence does not contain a leading 0, but does not mean that there is no digit 0 or digit ending in 0
      • For example, 00000, 101, 0121224, 1002102104206 and so on are cumulative numbers
    • Therefore, we need to categorize whether the first two digits of the string are 0
      • Case 1: The first two numbers are 0, as in:00XXXXIn this case, only the entire sequence is 0 is the cumulative number
      • Case 2: Only the first number is 0, e.g.012345In this case, the first number is determined, and the outer loop only needs one weight
      • Case 3: The first number is not 0, the second number can not be 0, such as:101,1002102104206In this case, the outer loop needs a double loop, that is, the first two numbers are changed
    • Among them, the continuous summation may lead to integer overflow, so special processing is needed to achieve high-precision addition
      • Method 1: Use strings to store and add analog digits
      • Method 2: Use arrays to store and add analog numbers

  • DFS + string high precision addition

    // Method one: DFS + string high precision addition
public boolean isAdditiveNumber(String num) {
    if (num == null || num.length() < 3) return false;
    String first = "", second = "", third = "";
    int n = num.length();
    boolean zeroFlag = false;
    // start with 00xxxx
    if (num.charAt(0) = ='0' && num.charAt(1) = ='0') {
        zeroFlag = true;
        for (int i = 2; i < n; i++) {
            if(num.charAt(i) ! ='0') return false;
        }
        // Start with 0xxxxx
    } else if (num.charAt(0) = ='0') {
        first = "0";
        for (int i = 2; i < n; i++) {
            second = num.substring(1, i);
            third = second;
            // System.out.println(third);
            if (dfs(second, third, num, i)) {
                return true; }}}else {
        // Nxxxxx = Nxxxxx
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j < n; j++) {
                first = num.substring(0, i);
                second = num.substring(i, j);
                // Prune: If there is a 0 at the beginning of Second, it is not possible to jump out of this loop and enter the outer loop as part of first
                if (second.length() > 1 && second.charAt(0) = ='0') break;
                // System.out.println(first + " " + second);
                third = getTarget(first, second);
                if (dfs(second, third, num, j)) {
                    return true; }}}}return zeroFlag;
}

private boolean dfs(String second, String third, String num, int index) {
    // DFS searches for the end of the string, which naturally ends with the sum true
    if (index == num.length()) return true;
    int len = third.length();
    // The length of the number to be found in the next search exceeds the remaining length of the string, false
    if (index + len > num.length()) return false;
    // Retrieves the number in the string equal to the length of the third to be searched
    String subStr = num.substring(index, index + len);
    // The search proceeds to the next round, otherwise false is returned
    if (third.equals(subStr)) {
        return dfs(third, getTarget(second, third), num, index + len);
    } else {
        return false; }}private String getTarget(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
    while (i >= 0 || j >= 0|| carry ! =0) {
        if (i >= 0) carry += num1.charAt(i--) - '0';
        if (j >= 0) carry += num2.charAt(j--) - '0';
        sb.append(carry % 10);
        carry /= 10;
    }
    String res = sb.reverse().toString();
    // System.out.println(res);
    return res;
}
Copy the code

  • Thought 1: the classification discussion section is very long at this time, can it be simplified

    • In the original version, the classification discussion about whether the first two numbers are 0 was passed directly on the outsideif-elseIt can be simplified to judge in the traversal process of the first two numbers and complete the classification discussion
    • For the first numberfirstIn traversal, we can determine the number of digits and whether the first digit is 0(leading 0). If so, we can return false, because only the sequence is00000All zeros are summative, and since we are in the second round of the outer loop, this case has been ruled out, and the sequence must not be summative
    • For the second numbersecond, in traversal, also determine the number of digits at this time, and whether the first digit is 0(leading 0), if so, directlybreakOut of the inner loop, continue traversing with the leading 0 as the end of the first number

  • Thought 2: Pruning during DFS

    • In fact, because of the third number in the summation sequencethirdIs the sum of the first two digits, so the number of digits in the third digit must be greater than or equal to the one with the largest median of the first two digitsthird.length() >= Math.max(first.length(), second.length()), which can be used for pruning
    • Pruning one: For the traversal of the first number, the number of digits should be less than or equal to half of the total sequence of cumulative numbers, so that the third number is possible, i.e. the loop variable of the outer loopi <= n / 2
    • Pruning 2: For the traversal of the second digit, there are certain requirements on the number of digits, that is, after the first two digits are removed, the remaining digits must be greater than or equal to the largest number of the first two digits
      • That is:n - j >= i,n - j >= j - i
      • There are:j <= Math.min(n - i, n / 2 + i / 2) + 1

  • Simplify + prune optimization: String addition and DFS search methods remain unchanged

    // Method 1: DFS+ string addition to achieve high-precision addition + pruning optimization, simplification
public boolean isAdditiveNumber(String num) {
    if (num == null || num.length() < 3) return false;
    String first = "", second = "", third = "";
    int n = num.length();
    // Simplify the classification discussion
    for (int i = 1; i <= n / 2; i++) {
        // 1. The value is 0xxxx and not 0000
        if (first.length() > 1 && first.charAt(0) = ='0') {
            return false;
        }
        for (int j = i + 1; j <= Math.min(n - i, n / 2 + i / 2) + 1; j++) {
            first = num.substring(0, i);
            second = num.substring(i, j);
            // 2. Corresponds to N0xxxx
            if (second.length() > 1 && second.charAt(0) = ='0') break;

            // 3. Other cases, including 0000 types
            third = getTarget(first, second);
            if (dfs(second, third, num, j)) {
                return true; }}}return false;
}
Copy the code

  • Thought 3: DFS and backtracking

    • Seeing that many students are confused about whether this is DFS or backtracking, I would like to share my humble opinion here
    • First of all, I think DFS and backtracking are actually a concrete realization of recursion. There is no real difference between them, but there are some differences in their ideas, so they are suitable for different types of questions and scenarios. Specifically
      • DFS is depth-first search, which is often used in binary tree, graph and other structures. Personally, DFS is written in the form of recursion instead of cycle and traversal, that is, analyzing possible answers one by one to find the final result, which is violent search
      • Backtracking is actually a violent search, but with a backtracking, trial-and-error concept in the application scenario, when an answer is not the answer we needSave&LoadBig method, get the first step of the answer, continue to search behind, such as permutation combination, subset, checkerboard maze and so on
    • For subject, before the match to determine whether a sequence is the third number, when the sum of two Numbers is a recursive search, belong to the DFS, at the same time, when the traverse every possible second number, the cycle is still not found as a result, at this time will move at the end of the first number subscript, originally on the part of the second number equivalent to the first number, It’s kind of a backtracking concept

3. Method 2: Non-recursive

  • In addition to the use of DFS recursive search, the problem can also be solved directly through the loop, traversal, that is, non-recursive form

  • Answer key

    public boolean isAdditiveNumber(String num) {
    if (num == null || num.length() < 3) return false;
    String first = "", second = "", third = "";
    int n = num.length();
    // Simplify the classification discussion
    for (int i = 1; i <= n / 2; i++) {
        // 1. The value is 0xxxx and not 0000
        if (first.length() > 1 && first.charAt(0) = ='0') {
            return false;
        }
        for (int j = i + 1; j <= Math.min(n - i, n / 2 + i / 2) + 1; j++) {
            first = num.substring(0, i);
            second = num.substring(i, j);
            // 2. Corresponds to N0xxxx
            if (second.length() > 1 && second.charAt(0) = ='0') break;
            // 3. Other cases, including 0000 types
            third = getTarget(first, second);
            // String rest = num.substring(j); // The rest of the sequence
            StringBuilder rest = new StringBuilder(num.substring(j)); // The rest of the sequence
            while(rest.indexOf(third) ! = -1) { // rest.startsWith(third)
                first = second;
                second = third;
                third = getTarget(first, second);
                // rest = rest.substring(second.length());
                rest.delete(0, second.length());
                if (rest.length() == 0) return true; }}}return false;
}

private String getTarget(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int carry = 0, i = num1.length() - 1, j = num2.length() - 1;
    while (i >= 0 || j >= 0|| carry ! =0) {
        if (i >= 0) carry += num1.charAt(i--) - '0';
        if (j >= 0) carry += num2.charAt(j--) - '0';
        sb.append(carry % 10);
        carry /= 10;
    }
    String res = sb.reverse().toString();
    // System.out.println(res);
    return res;
}
Copy the code

The last

  • Post a method with very little code from the community: Rainlight Java Traceback

    class Solution {
    public boolean isAdditiveNumber(String num) {
        return dfs(num, num.length(), 0.0.0.0);
    }

    / * * *@paramNum Original string *@paramLen Length of the original string *@paramIdx currently processes the subscript *@paramThe sum of the two digits before "sum" *@paramPre before the number *@paramK is the number currently processed */
    private boolean dfs(String num, int len, int idx, long sum, long pre, int k) {
        if (idx == len) {
            return k > 2;
        }
        for (int i = idx; i < len; i++) {
            long cur = fetchCurValue(num, idx, i);
            // Prune: invalid number
            if (cur < 0) {
                return false;
            }
            // Prune: The current number does not equal the sum of the previous two numbers
            if (k >= 2&& cur ! = sum) {continue;
            }
            if (dfs(num, len, i + 1, pre + cur, cur, k + 1)) {
                return true; }}return false;
    }

    /** * Get the valid digits from L to r */
    private long fetchCurValue(String num, int l, int r) {
        if (l < r && num.charAt(l) == '0') {
            return -1;
        }
        long res = 0;
        while (l <= r) {
            res = res * 10 + num.charAt(l++) - '0';
        }
        returnres; }}Copy the code

  • Related topics

    • LC842 splits the array into Fibonacci sequences
    • LC415 Adds the character string
    • LC2 and add them

By The Way

LeetCoder, a new developer, has published some problem solving solutions based on other developers’ ideas (links to resources are at the bottom). Please follow me if this article helps. I hope you can give me three even “like” & “favorites” & “attention” ~ ~ ~ also hope you have time to visit my “personal blog”.