My java solution, handle large numbers, w/o BigInteger, 2ms


  • 0
    M
    public class Solution {
        public String add(String num1, String num2) {
            int carry = 0;
            int i1 = num1.length() - 1; 
            int i2 = num2.length() - 1;
            StringBuffer result = new StringBuffer();
            while (i1 >= 0 || i2 >= 0) {
                int d1 = (i1 >= 0) ? num1.charAt(i1) - '0' : 0;
                int d2 = (i2 >= 0) ? num2.charAt(i2) - '0' : 0;
                int d3 = d1 + d2 + carry;
                carry = d3 / 10;
                result.append(d3 % 10);
                i1--; i2--;
            }
            
            if (carry > 0) result.append(carry);
            return result.reverse().toString();
        }
        
        public boolean build(String prev1, String prev2, int idx, String num) {
            if (idx == num.length()) return true;
            
            String next = add(prev1, prev2);
            if (num.indexOf(next, idx) == idx) {
                if (build(prev2, next, idx + next.length(), num)) return true;
            }
            
            return false;
        }
        public boolean isAdditiveNumber(String num) {
            int n = num.length();
            if (n == 0) return false;
            for(int i = 1; i < n; i++) {
                String str1 = num.substring(0, i);
                if (str1.length() > 1 && str1.charAt(0) == '0') break;
                for(int j = i + 1; j < n; j++) {
                    String str2 = num.substring(i, j);
                    if (str2.length() > 1 && str2.charAt(0) == '0') continue;
                    if (build(str1, str2, j, num)) return true;
                }
            }
            return false;
        }
    }

Log in to reply
 

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