I believe my code has bugs but it Accepted


  • 0
    L

    For the input "199111992" the result should be true but the result of my code is false, and for the input "199001200" the result should be false but the result of my code is true

    public boolean isAdditiveNumber(String num) {
    		if (num.length() < 3)
    			return false;
    		for (int i = 1; i < num.length() / 3 + 1; i++)
    			for (int j = i + 1; j < num.length() * 2 / 3 + 1; j++)
    				if (aux(num, i, j))
    					return true;
    		return false;
    	}
    
    	private boolean aux(String num, int start, int end) {
    		if (end == num.length())
    			return true;
    		String res = add(num.substring(0, start), num.substring(start, end));
    		if (num.length() >= end + res.length()
    				&& res.equals(num.substring(end, end + res.length())))
    			return aux(num.substring(start), end - start, end + res.length()
    					- start);
    		else
    			return false;
    	}
    	
    	private static String add(String a, String b) {
    		int n = Math.max(a.length(), b.length());
    		boolean aLong = a.length() > b.length();
    		int differ = aLong ? a.length() - b.length() : b.length() - a.length();
    		int carry = 0;
    		char[] res = new char[n + 1];
    		for (int i = n; i >= 0; i--) {
    			int iFirst = aLong ? i - 1 : i - 1 - differ;
    			int iSecond = aLong ? i - 1 - differ : i - 1;
    			char first = iFirst >= 0 ? a.charAt(iFirst) : '0';
    			char second = iSecond >= 0 ? b.charAt(iSecond) : '0';
    			int tmp = first + second + carry - '0' * 2;
    			res[i] = (char) (tmp % 10 + '0');
    			carry = tmp > 9 ? 1 : 0;
    		}
    		String result = new String(res);
    		return result.charAt(0) == '0' ? result.substring(1) : result;
    	}
    ...
    
    So I modify my code
    ...
    public boolean isAdditiveNumber(String num) {
    		if (num.length() < 3)
    			return false;
    		for (int i = 1; i < num.length() / 2 + 1; i++)
    			for (int j = i + 1; j < num.length() * 2 / 3 + 1; j++)
    			    if ( i + 1 == j || num.charAt(i) != '0' && num.charAt(j) != '0')
    				    if (aux(num, i, j))
    					    return true;
    		return false;
    	}
    
    	private boolean aux(String num, int start, int end) {
    		if (end == num.length())
    			return true;
    		String res = add(num.substring(0, start), num.substring(start, end));
    		if (num.length() >= end + res.length()
    				&& res.equals(num.substring(end, end + res.length())))
    			return aux(num.substring(start), end - start, end + res.length()
    					- start);
    		else
    			return false;
    	}
    	
    	private String add(String a, String b) {
    		int n = Math.max(a.length(), b.length());
    		boolean aLong = a.length() > b.length();
    		int differ = aLong ? a.length() - b.length() : b.length() - a.length();
    		int carry = 0;
    		char[] res = new char[n + 1];
    		for (int i = n; i >= 0; i--) {
    			int iFirst = aLong ? i - 1 : i - 1 - differ;
    			int iSecond = aLong ? i - 1 - differ : i - 1;
    			char first = iFirst >= 0 ? a.charAt(iFirst) : '0';
    			char second = iSecond >= 0 ? b.charAt(iSecond) : '0';
    			int tmp = first + second + carry - '0' * 2;
    			res[i] = (char) (tmp % 10 + '0');
    			carry = tmp > 9 ? 1 : 0;
    		}
    		String result = new String(res);
    		return result.charAt(0) == '0' ? result.substring(1) : result;
    	}
    

  • 0

    @ljj19921026 Thanks, I have added your test cases.


Log in to reply
 

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