Easy understanding iterative solution


  • 0
    2

    Firstly use 2 loops to pick up the initial 2 number, and then use another loop to add them 1 by 1. Easy to understand. it is easy to update for the followup.

    public boolean isAdditiveNumber(String num) {
        if (num == null) {
            return false;
        }
        
        int len = num.length();
        
        if (len == 0 || num.charAt(0) == '0') {
            return false;
        }
        
        String lastTwo;
        String lastOne;
        String cur;
        
        for (int i = 0;i < len - 2;i++) {
            
            for (int j = i + 1;j < len - 1;j++) {
                
                lastTwo = num.substring(0, i + 1);
                lastOne = num.substring(i + 1, j + 1);
                
                if (lastOne.length() > 1 && lastOne.charAt(0) == '0') {
                    break;
                }
    
                
                int head = j + 1;
                
                for (int k = head;k < len;k++) {
                    
                    cur = num.substring(head, k + 1);
                    
                    if (cur.length() > 1 && cur.charAt(0) == '0') {
                        break;
                    }
                    
                    long curLong = Long.parseLong(cur);
                    long sum = sum(lastTwo, lastOne);
                    
                    if (sum == curLong) {
                        
                        if (k == len - 1) {
                            return true;
                        }
                        
                        lastTwo = lastOne;
                        lastOne = cur;
                        head = k + 1;
                    } else if (sum < curLong) {
                        break;
                    }
                }
                
            }
        }
        
        return false;
    }
    
    public long sum(String s1, String s2) {
        return Long.parseLong(s1) + Long.parseLong(s2);
    }

Log in to reply
 

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