JAVA iterative solution beat 98.8% using "long" to handle overflow


  • 0
    T
     public boolean isAdditiveNumber(String num) {
            if (num.length() < 3) return false;
            int end = num.length() / 3 * 2; //the end of each circle
            long num1 = 0;
            char n1 = num.charAt(0);
            for (int i = 0 ; i < end;) {
                if (n1 == '0' && i != 0) {
                    return false;
                }
                num1 = num1 * 10 + (num.charAt(i) - 48);
                long num2 = 0;
                char n2 = num.charAt(i + 1);
                for (int j =i + 1; j < end;) {
                    if (n2 == '0' && j != i + 1) {
                        break;
                    }
                    num2 = num2 * 10 + (num.charAt(j) - 48);
                    long sum = num1 + num2;
                    if (analyse(sum, num2, j + 1, num)) {
                        return true;
                    }
                    j ++;
                }
                i ++;
            }
            return false;
        }
        
        private boolean analyse(long sum, long num2, int j, String num) {
            if (j == num.length()) {
                return true;
            }
            //02,03 ...
            if (num.charAt(j) == '0' && sum != 0) {
                return false;
            }
            long tag = 0;
            for (; j < num.length(); j ++) {
                tag = tag * 10 + (num.charAt(j) - 48);
                if (tag < sum) {
                    continue;
                }
                if (tag == sum) {
                    return analyse(sum + num2, sum, j + 1, num);
                }
                if (tag > sum) {
                    return false;
                }
            }
            return false;
        }
    

Log in to reply
 

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