A recursive comparator with explanation


  • 0
    L

    We sort the strings based on the lexical order of each letter in the strings. If a string “a” is a prefix of the other string “b”, then we compare the the postfix of “b” with “a” recursively.

    e.g. a = “2”, b = “2281”.

    a is a prefix of b, then we go on to compare the postfix of b’=“281” with a=“2”. Again, a is a prefix of b’. We then compare b’’=“81” with a=“2”. This time, we know b’’ should be placed before a.

    At the end, we know we could obtain a bigger number 2281|2 (vs. 2|2281), when placing b before a.

    Voila. Here is the code.

    class NumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            int al = a.length();
            int bl = b.length();
        	int i = 0;
        	while(i<al && i<bl){
        		if(a.charAt(i) > b.charAt(i)){
        			return 1;
        		}else if(a.charAt(i) < b.charAt(i)){
        			return -1;
        		}
        		// a.charAt(i) == b.charAt(i)
        		++i;
        	}
        	
        	if(al == bl){
        		return 0;
        	}else if(al < bl){
        		return compare(a, b.substring(i));
        	}else{
        		return compare(a.substring(i), b);
        	}
        }
    }
    
    public String largestNumber(int[] num) {
    	ArrayList<String> nums = new ArrayList<String>();
    	for(int i : num){
    		nums.add(String.valueOf(i));
    	}
    	
    	Collections.sort(nums, new NumberComparator());
    	
    	StringBuffer res = new StringBuffer();
    	
    	for(int i=nums.size()-1; i>=0; --i){
    		res.append(nums.get(i));
    	}
    	
    	// if all zeros, then return only a single zero
    	if(res.length() > 0 && res.charAt(0) == '0'){
    		return "0";
    	}else{
    		return res.toString();
    	}
    }

  • 0
    L

    There is another option of implementing the comparator, which is to concatenate the two strings in two different ways, and then compare the two results of the same length directly with the build-in comparison function of String.

    e.g. a = “2”, b = “2281”.

    ab = “22281”

    ba = “22812”

    class CombinationComparator implements Comparator<String> {
    	    @Override
    	    public int compare(String a, String b) {
    	        String ab = a + b;
    	        String ba = b + a;
    	        
    	        // Compare directly two options of combination.
    	    	return ab.compareTo(ba);
    	    }
    }
    

  • 0
    H

    Thanks! I got it


Log in to reply
 

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