[数据结构与算法]306. 累加数-leetcode自解(DFS)

领悟：

1. 一串符号，如果每个分支与index有关，就可以用for循环。
2. for循环内部，无论在递归算法内部实现哪个地方返回false，都会在返回到的那个节点执行后面的代码，也就是换分支。
3. 如果想控制递归到树的底部返回的时候不走父节点分支，也就是原路返回，使用如下demo：

if (dfs(num, i + 1)) {
                    return true;
                }

解题：

class Solution {
     private  List<String> res = new ArrayList<>();

    public  boolean isAdditiveNumber(String num) {
        //开始递归
        int start = 0;
        return dfs(num , start);
    }

    public  boolean isValid(String num) {
        if (num.length() > 1 && num.charAt(0) == '0') {
            return false;
        }
        return true;
    }
    public  boolean dfs(String num , int start) {
        //1.数组个数超过三，判断前两个相加是否等于第三个
        int size = res.size();
        //2.中途
        if (size >= 3) {
            if (!res.get(size - 1).equals(addStr(res.get(size - 2), res.get(size - 3)))) {
                return false;
            }
            //结尾:注意这里的判断，不是size == start+1
            if (num.length() == start) {
                return true;
            }
        }

        for (int i = start ; i < num.length() ; i++) {
            String substring = num.substring(start, i + 1);
            // 找到了一组解就提前结束
            if (isValid(substring)) {
                res.add(substring);
                if (dfs(num, i + 1)) {
                    return true;
                }
                res.remove(res.size() - 1);
            }
        }
        return false;
    }

    public  String addStr(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int carry = 0;
        while(i >= 0 || j >= 0) {
            int a = i >= 0 ? num1.charAt(i) - '0' : 0;
            int b = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = a + b + carry;
            carry = sum / 10;
            result.append(sum % 10);
            i--;
            j--;
        }
        if (carry > 0) {
            result.append(carry);
        }
        return result.reverse().toString();
    }
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖