Java Accepted 1ms, no BigInteger or Long needed.


  • 0
    D

    The idea is to choose i, j, k as the beginning of three string s1, s2, s3. If we see any combination s1 + s2 == s3, we move forward and compare s2 + s3 with s4 (the next possible number). i is 0 at first.

    public class Solution {
        public boolean isAdditiveNumber(String num) {
            if (num == null) return false;
            int n = num.length();
            if (n == 0) return false;
            int half = (n - 1) >> 1;
            for (int j = 1; j <= half; j++) {
                for (int k = j + 1; k <= n - j && k + k <= n + j; k++) {
                    if (dfs(num, 0, j, k))
                        return true;
                }
            }
            return false;
        }
        boolean dfs(String s, int i, int j, int k) {
            if (k == s.length()) return true;
            if (k > s.length()) return false;
            if (s.charAt(i) == '0' && j > i + 1) return false;
            if (s.charAt(j) == '0' && k > j + 1) return false;
            if (s.charAt(k) == '0') return false;
            String s1 = s.substring(i, j);
            String s2 = s.substring(j, k);
            int maxLen = Math.max(j-i, k-j);
            if (k + maxLen > s.length()) 
            	return false;
            String s3 = s.substring(k, k + maxLen);
            if (equals(s1, s2, s3)) {
                return dfs(s, j, k, k + maxLen);
            }
            if (k + maxLen + 1 > s.length()) 
            	return false;
            String s4 = s.substring(k, k + maxLen + 1);
            if (equals(s1, s2, s4)) {
                return dfs(s, j, k, k + maxLen + 1);
            } else
                return false;
        }
        boolean equals(String s1, String s2, String s3) {
            char[] w1 = s1.toCharArray();
            char[] w2 = s2.toCharArray();
            char[] w3 = s3.toCharArray();
            int len1 = w1.length, len2 = w2.length, len3 = w3.length;
            if (len3 < Math.max(len1, len2)) return false;
            if (len3 > Math.max(len1, len2) + 1) return false;
            if (len1 < len2) {
            	char[] temp = w2;
            	w2 = w1;
            	w1 = temp;
            	int temp2 = len1;
            	len1 = len2;
            	len2 = temp2;
            }
            int i;
            int carry = 0;
            for(i = 0; i < len2; i++) {
            	int sum = w1[len1 - i - 1] - '0' + w2[len2 - i - 1] - '0' + carry;
            	if (sum < 10) {
            		if (sum != w3[len3 - i - 1] - '0')
            			return false;
            		carry = 0;
            	} else {
            		sum = sum - 10;
            		carry = 1;
            		if (sum != w3[len3 - i - 1] - '0')
            			return false;
            	}
            }
            for (; i < len1; i++) {
            	int sum = w1[len1 - 1 - i] - '0'+ carry;
            	if (sum < 10) {
            		if (sum != w3[len3 - 1 - i] - '0')
            			return false;
            		carry = 0;
            	} else {
            		sum -= 10;
            		carry = 1;
            		if (sum != w3[len3 - 1 - i] - '0')
            			return false;
            	}
            }
            if (len1 == len3) {
            	if (carry  == 1) return false;
            } else {
            	if (carry != w3[len3 - 1 - i] - '0')
            		return false;
            }
            return true;
        }
    }

  • 0
    G

    So what will happen to 112233?

    In your idea you will find 1+1=2 first then return false.

    But the correct answer is 11+22=33.


Log in to reply
 

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