Concise iterative solution with Queue


  • 0
    S

    Find (i, j, k) that defines first two numbers that add up to the third number then move (i, j, k) with new k value found from the third number.

    public boolean isAdditiveNumber(String s) {
        if (s.length() < 3) return false;
    
        int i = 0;
        for (int j = i + 1; j < s.length() - 1; j++) {
            for (int k = j + 1; k < s.length(); k++) {
    
                Q q = new Q(i, j, k);
                q.addNewK(addUp(s, i, j, k));
                while (q.k() != -1 && q.k() < s.length())
                    q.addNewK(addUp(s, q.i(), q.j(), q.k()));
    
                if (q.k() == s.length())
                    return true;
            }
        }
    
        return false;
    }
    
    class Q {
        int x = 0;
        int q[];
    
        public Q(int i, int j, int k) { q = new int[]{i, j, k}; }
    
        int i() { return q[x % 3]; }
        int j() { return q[(x + 1) % 3]; }
        int k() { return q[(x + 2) % 3]; }
    
        void addNewK(int k) { x++; q[(x + 2) % 3] = k; }
    }
    
    private int addUp(String s, int i, int j, int k) {
        if ((s.charAt(i) == '0' && j - i > 1) || (s.charAt(j) == '0' && k - j > 1)) return -1;
        String sum = "" + (Long.parseLong(s.substring(i, j)) + Long.parseLong(s.substring(j, k)));
        return s.substring(k).startsWith(sum) ? k + sum.length() : -1;
    }

Log in to reply
 

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