Java Solution using Recursion


  • 0
    Z
    public class Solution {
        public boolean isAdditiveNumber(String num) {
            return isValid(num,0,new ArrayList<String>());
        }
        
        public boolean isValid(String num, int index, List<String> pre) {
            if(index == num.length() && pre.size() >= 3) return true;
            if(index == num.length() ) return false;
            for(int i = index+1; i<=num.length();i++) {
                if(num.charAt(index) == '0' && i-index > 1) continue;
                String cur = num.substring(index,i);
                if(pre.size() < 2) {
                    pre.add(cur);
                    if(isValid(num,i,pre)) return true;
                    pre.remove(pre.size()-1);
                } else {
                    int n = pre.size()-1;
                    String first = pre.get(n-1);
                    String second = pre.get(n);
                    if(sumEqual(first,second,cur) ) {
                        pre.add(cur);
                        if(isValid(num,i,pre)) return true;
                        pre.remove(pre.size()-1);
                    }
                }
            }
            return false;
        }
        public boolean sumEqual(String s1,String s2,String s3) {
            int carry = 0;
            String sum = "";
            for(int i = s1.length()-1,j=s2.length()-1;i>=0||j>=0;i--,j--) {
                if(i < 0) {
                    int v = s2.charAt(j)-'0' + carry;
                    int a = v%10;
                    carry = v/10;
                    sum = ""+a + sum;
                } else if(j < 0) {
                    int v = s1.charAt(i)-'0' + carry;
                    int a = v%10;
                    carry = v/10;
                    sum = ""+a + sum;
                } else {
                    int v = s2.charAt(j)-'0'+s1.charAt(i)-'0' + carry;
                    int a = v%10;
                    carry = v/10;
                    sum = ""+a + sum;
                }
            }
            if(carry != 0) sum = ""+carry+sum;
            return sum.equals(s3);
        }
        
    }
    

Log in to reply
 

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