1ms Solution without using long or big integer


  • 0
    R
    class Solution {
        public boolean isAdditiveNumber(String num) {
            int m = num.length();
            for(int i = 0; i < m / 2; ++i) {
                String left = num.substring(0, i + 1);
                for(int j = i + 1; j < (i + 1 + (m - i - 1) / 2); ++j) {
                    String right = num.substring(i + 1, j + 1);
                    if(helper(num, j + 1, left, right)) {
                        return true;
                    }
                    if(num.charAt(i + 1) == '0') {
                        break;
                    }
                }
                if(num.charAt(0) == '0') {
                    break;
                }
            }
            return false;
        }
        
        private boolean helper(String num, int start, String left, String right) {
            String res = sum(left, right);
            int m = res.length();
            int n = num.length();
            int j = 0, i = start;
            while(i < n && j < m) {
                if(res.charAt(j) != num.charAt(i)) {
                    break;
                }
    
                if(num.charAt(start) == '0') {
                    ++i;
                    ++j;
                    break;
                }
                ++i;
                ++j;
            }
            if(j != m) {
                return false;
            }
            if(i == n) {
                return true;
            }
            return helper(num, i, right, res);
        }
        private String sum(String left, String right) {
            int m = left.length();
            int n = right.length();
            int k = Math.max(m, n) + 1;
            char[] tempRes = new char[k];
            int c = 0;
            int i = m - 1, j = n - 1;
            int l = k;
            while(i >= 0 || j >= 0) {
                int num1 = i >= 0 ? left.charAt(i--) - '0' : 0;
                int num2 = j >= 0 ? right.charAt(j--) - '0' : 0;
                int sum = num1 + num2 + c;
                c = sum / 10;
                sum = sum % 10;
                tempRes[--l] = (char)(sum + '0');
                
            }
            if(c != 0) {
                tempRes[--l] = (char)(c + '0');
            }
            StringBuilder res = new StringBuilder();
            while(l < k) {
                res.append(tempRes[l++]);
            }
            return res.toString();
        }
    }
    

Log in to reply
 

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