SHARE
TWEET

sharfah

a guest Apr 9th, 2010 268 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedOutputStream;
  2. import java.io.FileDescriptor;
  3. import java.io.FileOutputStream;
  4. import java.io.PrintStream;
  5. import java.math.BigInteger;
  6. import java.util.Scanner;
  7.  
  8. public class Main {
  9.    
  10.     /**
  11.      * Brute Force method.
  12.      * Keeps incrementing by one until a palindrome is found.
  13.      * @param s
  14.      * @return the next palindrome
  15.      */
  16.     public static String bruteForce(String s){
  17.         BigInteger i = new BigInteger(s) ;
  18.         while(true){
  19.             i = i.add(BigInteger.ONE);
  20.             String result = i.toString();
  21.             if(isPalindrome(result)){
  22.                 return result;
  23.             }
  24.         }
  25.     }
  26.    
  27.     /**
  28.      * Mirrors a string around the centre.
  29.      * Example: abc -> aba and abcd -> abba
  30.      * @param s
  31.      * @return mirrored string
  32.      */
  33.     public static String mirror(String s) {
  34.         final char[] arr = s.toCharArray();
  35.         int midpoint = arr.length / 2;
  36.         int i = arr.length % 2 == 0 ? midpoint : midpoint + 1;
  37.         while (i < arr.length) {
  38.             arr[i] = arr[midpoint - 1];
  39.             i++;
  40.             midpoint--;
  41.         }
  42.         return new String(arr);
  43.     }
  44.    
  45.     /**
  46.      * Increments the middle digit.
  47.      * Example: 12345 -> 12445 and 1234 -> 1334
  48.      * 9s get incremented to 0 and carried over.
  49.      * Example: 12945 -> 13045
  50.      * @param s
  51.      * @return incremented string
  52.      */
  53.     public static String incrementFromMiddle(String s) {
  54.  
  55.         final char[] arr = s.toCharArray();
  56.         final int midpoint = arr.length / 2;
  57.         int currPoint = arr.length % 2 == 0 ? midpoint - 1 : midpoint;
  58.         boolean found = false;
  59.  
  60.         while (currPoint >= 0 && !found) {
  61.             char c = arr[currPoint];
  62.             char inc;
  63.             if (c == '9') {
  64.                 inc = '0';
  65.             }
  66.             else {
  67.                 inc = (char) (c + 1);
  68.                 found = true;
  69.             }
  70.             arr[currPoint] = inc;
  71.             if (!found) {
  72.                 currPoint--;
  73.             }
  74.         }
  75.  
  76.         if (!found) {
  77.             // we have fallen off the start of the string
  78.             // example 999 has become 009. Add a one on to give: 1009
  79.             final char[] newarr = new char[arr.length + 1];
  80.             newarr[0] = '1';
  81.             System.arraycopy(arr, 0, newarr, 1, arr.length);
  82.             return new String(newarr);
  83.         }
  84.         else {
  85.             return new String(arr);
  86.         }
  87.     }
  88.    
  89.    
  90.    
  91.     /**
  92.      * Next Palindrome using the mirroring approach.
  93.      * @param s
  94.      * @return
  95.      */
  96.     public static String getNextPalindrome(String s) {
  97.         String mirrored = mirror(s);
  98.  
  99.         //the mirror might be smaller than original, so increment it and try again.
  100.         if (compare(mirrored, s) <= 0) {
  101.             mirrored = mirror(incrementFromMiddle(s));
  102.         }
  103.         return mirrored;
  104.     }
  105.    
  106.     /**
  107.      * @param s
  108.      * @return true if the specified string is a palindrome.
  109.      */
  110.     private static boolean isPalindrome(String s) {
  111.         //compare first and last chars, second and second-last and so on.
  112.         for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
  113.             if (s.charAt(i) != s.charAt(j)) {
  114.                 return false;
  115.             }
  116.         }
  117.         return true;
  118.     }
  119.    
  120.     /**
  121.      * Compares two numerical mirrored strings.
  122.      * Assumes they have the same length.
  123.      * Only compares the second half of the strings.
  124.      * @param s
  125.      * @param t
  126.      * @return -1, 0 or 1 if s<t, s==t or s>t
  127.      */
  128.     private static int compare(String s, String t){
  129.         //only check second half
  130.         int midpoint = s.length() / 2;
  131.         int i = s.length() % 2 == 0 ? midpoint : midpoint + 1;
  132.         for (; i < s.length(); i++) {
  133.             if(s.charAt(i) < t.charAt(i)){
  134.                 return -1 ;
  135.             }
  136.             else if (s.charAt(i) > t.charAt(i)){
  137.                 return 1;
  138.             }
  139.         }
  140.         return 0;
  141.     }
  142.    
  143.     /**
  144.      * The main method.
  145.      *
  146.      * @param args
  147.      */
  148.     public static void main(String[] args) {
  149.         // fast output as there is no flush on \n
  150.         final FileOutputStream fdout = new FileOutputStream(FileDescriptor.out);
  151.         final BufferedOutputStream bos = new BufferedOutputStream(fdout, 1024);
  152.         final PrintStream ps = new PrintStream(bos, false);
  153.         System.setOut(ps);
  154.        
  155.         try {
  156.             final Scanner scanner = new Scanner(System.in);
  157.             scanner.next();
  158.             while (scanner.hasNext()) {
  159.                 final String s = scanner.next();
  160.                 System.out.println(getNextPalindrome(s));
  161.             }
  162.         }
  163.         catch (Exception e) {
  164.             e.printStackTrace();
  165.         }
  166.         finally {
  167.             ps.close();
  168.         }
  169.     }
  170. }
RAW Paste Data
Top