Java Straight forward solution


  • 0
    Z

    This code quite dirty and needs refactoring. However it is very strightforward.
    The idea is, just take half of the string, then get minimum palindrome string, that can be obtained by incrementing each digit one by one and mirroring. The same operation is done for decrementing. At last do not forget the edge cases with string '99..9' with length n.length()-1 and '1000..0001' with length n.length()+1.
    Good question is why we increment only one digit at a time? Answer is, because we need minimum difference. It is easy to prove that minimum diff can be obtained only by changing one digit except edge cases.

    public class Solution {
        public String nearestPalindromic(String n) {
            if(n == null) return n;
            String inc = getNearestByInc(n, 1, '9');
            String dec  = getNearestByInc(n,-1,'0');
            
            StringBuilder spec = new StringBuilder();
            for(int i = 0;i<n.length()-1;i++) spec.append('9');
            String str= spec.toString();
            spec.setLength(0);
            spec.append('1');
            for(int i = 0;i<n.length()-1;i++) spec.append('0');
            spec.append('1');
            String str2 = spec.toString();
            if(Math.abs(Long.parseLong(dec)-Long.parseLong(n)) <= Math.abs(Long.parseLong(inc)-Long.parseLong(n))){
                if(!str.isEmpty() && Math.abs(Long.parseLong(dec)-Long.parseLong(n)) >= Math.abs(Long.parseLong(str)-Long.parseLong(n))){
                    return str;
                }
                if(Math.abs(Long.parseLong(dec)-Long.parseLong(n)) >= Math.abs(Long.parseLong(str2)-Long.parseLong(n))){
                    return str2;
                }
                return dec;
            }
             if(!str.isEmpty() && Math.abs(Long.parseLong(inc)-Long.parseLong(n)) >= Math.abs(Long.parseLong(str)-Long.parseLong(n))){
                    return str;
                }
            if(Math.abs(Long.parseLong(inc)-Long.parseLong(n)) > Math.abs(Long.parseLong(str2)-Long.parseLong(n))){
                    return str2;
            }
            return inc;
        }
        
        private String getNearestByInc(String n, int inc, char tresh){
            int mid = n.length()/2;
            StringBuilder pal = new StringBuilder();
            StringBuilder res = new StringBuilder();
            pal.append(n.substring(0,mid));
            res.append(pal);
            if(n.length()%2 == 1) res.append(n.charAt(mid));
            res.append(pal.reverse());
            String maxStr = res.toString();
            long val = Long.parseLong(n);
            long minDiff = Math.abs(val-Long.parseLong(maxStr));
            if(maxStr.equals(n)){
                maxStr = "0";
                minDiff = Math.abs(val-Long.parseLong(maxStr));
            }
            for(int i = mid-1;i>=0;i--){
                if(n.charAt(i) == tresh) continue;
                pal.setLength(0);
                res.setLength(0);
                pal.append(n.substring(0,i));
                pal.append((char)(n.charAt(i)+inc));
                for(int j = i+1;j<mid;j++) pal.append('0');
                res.append(pal);
                if(n.length()%2 == 1) res.append('0');
                res.append(pal.reverse());
                String str = res.toString();
                long diff = Math.abs(val-Long.parseLong(str));
                if(diff < minDiff){
                    maxStr = str;
                    minDiff = diff;
                } else if(diff == minDiff){
                    if(Long.parseLong(maxStr) > Long.parseLong(str)){
                        maxStr = str;
                    }
                } 
            }
            pal.setLength(0);
            res.setLength(0);
            if(n.length()%2 == 1 && n.charAt(mid) != tresh){
                pal.append(n.substring(0,mid));
                res.append(pal);
                res.append((char)(n.charAt(mid)+inc));
                res.append(pal.reverse());
                String str = res.toString();
                long diff = Math.abs(val-Long.parseLong(str));
                if(diff < minDiff){
                    maxStr = str;
                    minDiff = diff;
                } else if(diff == minDiff){
                    if(Long.parseLong(maxStr) > Long.parseLong(str)){
                        maxStr = str;
                    }
                } 
            }
            return maxStr;
        }
    }

Log in to reply
 

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