Share my java AC solution, avoid using integer plus.


  • 0
    S
    public boolean isAdditiveNumber(String num) {
            int n = num.length();
            for (int i = 0; i < n - 2; i++) {
                for (int j = i + 1; j < n - 1; j++) {
                    if (isAdditiveNumber(num.substring(j + 1), num.substring(0, i + 1), 
                        num.substring(i + 1, j + 1))) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean isAdditiveNumber(String num, String first, String second) {
            String sum = getSum(first, second);
            if (num.length() < sum.length()) {    // check remaining size
                return false;
            } else if (num.length() == sum.length()) {    // end of string
                return num.equals(sum);
            }
            if (sum.equals(num.substring(0, 0 + sum.length()))) {
                return isAdditiveNumber(num.substring(sum.length()), second, sum);
            } else {
                return false;
            }
        }
    
        // the same method adding two string
        private String getSum(String first, String second) {
            StringBuilder sum = new StringBuilder();
            int index1 = first.length() - 1;
            int index2 = second.length() - 1;
            int carry = 0;
            while (index1 >= 0 || index2 >= 0 || carry != 0) {
                int val1 = index1 >= 0 ? (first.charAt(index1--) - '0') : 0;
                int val2 = index2 >= 0 ? (second.charAt(index2--) - '0') : 0;
                int cur = (val1 + val2 + carry) % 10;
                carry = (val1 + val2 + carry) / 10;
                sum.insert(0, cur);
            }
            return sum.toString();
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.