🌕 306. 累加数

难度: 🌕

问题描述

---

解法

class Solution {
    public boolean isAdditiveNumber(String num) {
        // 思路：
        // 回溯
        int len = num.length();
        return mySol(num, len, 0, -1, -1, false);
    }

    private boolean mySol(String num, int len, int index, long a, long b, boolean flag) {
        // System.out.println(index + " " + a + " " + b + " " + flag);
        // 递归终止条件
        if(index == len) {
            return flag; // flag 表示当前轮不止有 a & b，还得到了一个 c 
        }
        if(a == -1) {
            if(num.charAt(index) == '0') {
                return mySol(num, len, index + 1, 0l, b, flag);
            }
            for(int i = index; i < len - 1; i ++) {
                a = Long.parseLong(num.substring(index, i + 1));
                if(mySol(num, len, i + 1, a, b, flag)) {
                    return true;
                }
            }
            return false;
        } else if(b == -1) {
            if(num.charAt(index) == '0') {
                return mySol(num, len, index + 1, a, 0l, flag);
            }
            for(int i = index; i < len; i ++) {
                b = Long.parseLong(num.substring(index, i + 1));
                if(mySol(num, len, i + 1, a, b, flag)) {
                    return true;
                }
            }
            return false;
        } else {
            // a & b 均已有值，截取 c
            long c = a + b;
            String cur = String.valueOf(c);
            int tmpLen = cur.length();
            if(index + tmpLen - 1 >= len) {
                return false;
            } else if(num.substring(index, index + tmpLen).equals(cur)) {
                // 累加和匹配，继续往下递归
                return mySol(num, len, index + tmpLen, b, c, true);
            } else {
                return false;
            }
        }
    }
}

---

输出

---

进阶问题

• 转换为 字符串的加法