java - saber - Un mejor algoritmo para encontrar el siguiente palíndromo de una cadena numérica

programa de palindromo en netbeans

Question

Primero, este es el problema:

Un entero positivo se llama palíndromo si su representación en el sistema decimal es la misma cuando se lee de izquierda a derecha y de derecha a izquierda. Para un entero positivo positivo K de no más de 1000000 dígitos, escriba el valor del palíndromo más pequeño que K para la salida. Los números siempre se muestran sin ceros a la izquierda.

Entrada: la primera línea contiene el número entero t, el número de casos de prueba. Los enteros K se dan en las siguientes líneas t.

Salida: para cada K, da salida al palíndromo más pequeño mayor que K. Ejemplo

Entrada:

2

808

2133

Salida:

818

2222

En segundo lugar, aquí está mi código:

// I know it is bad practice to not cater for erroneous input,
// however for the purpose of the execise it is omitted
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.Exception;
import java.math.BigInteger;
public class Main
{
public static void main(String [] args){
try{
Main instance = new Main(); // create an instance to access non-static
// variables
// Use java.util.Scanner to scan the get the input and initialise the
// variable
Scanner sc=null;
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
String input = "";
int numberOfTests = 0;
String k; // declare any other variables here
if((input = r.readLine()) != null){
sc = new Scanner(input);
numberOfTests = sc.nextInt();
}
for (int i = 0; i < numberOfTests; i++){
if((input = r.readLine()) != null){
sc = new Scanner(input);
k=sc.next(); // initialise the remainder of the variables sc.next()
instance.palindrome(k);
} //if
}// for
}// try
catch (Exception e)
{
e.printStackTrace();
}
}// main
public void palindrome(String number){
StringBuffer theNumber = new StringBuffer(number);
int length = theNumber.length();
int left, right, leftPos, rightPos;
// if incresing a value to more than 9 the value to left (offset) need incrementing
int offset, offsetPos;
boolean offsetUpdated;
// To update the string with new values
String insert;
boolean hasAltered = false;
for(int i = 0; i < length/2; i++){
leftPos = i;
rightPos = (length-1) - i;
offsetPos = rightPos -1; offsetUpdated = false;
// set values at opposite indices and offset
left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
if(left != right){
// if r > l then offest needs updating
if(right > left){
// update and replace
right = left;
insert = Integer.toString(right);
theNumber.replace(rightPos, rightPos + 1, insert);
offset++; if (offset == 10) offset = 0;
insert = Integer.toString(offset);
theNumber.replace(offsetPos, offsetPos + 1, insert);
offsetUpdated = true;
// then we need to update the value to left again
while (offset == 0 && offsetUpdated){
offsetPos--;
offset =
Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
offset++; if (offset == 10) offset = 0;
// replace
insert = Integer.toString(offset);
theNumber.replace(offsetPos, offsetPos + 1, insert);
}
// finally incase right and offset are the two middle values
left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
if (right != left){
right = left;
insert = Integer.toString(right);
theNumber.replace(rightPos, rightPos + 1, insert);
}
}// if r > l
else
// update and replace
right = left;
insert = Integer.toString(right);
theNumber.replace(rightPos, rightPos + 1, insert);
}// if l != r
}// for i
System.out.println(theNumber.toString());
}// palindrome
}

Finalmente mi explicación y pregunta.

My code compares either end and then moves in
if left and right are not equal
if right is greater than left
(increasing right past 9 should increase the digit
to its left i.e 09 ---- > 10) and continue to do
so if require as for 89999, increasing the right
most 9 makes the value 90000
before updating my string we check that the right
and left are equal, because in the middle e.g 78849887
we set the 9 --> 4 and increase 4 --> 5, so we must cater for this.

El problema es de spoj.pl un sistema de jueces en línea. Mi código funciona para todo lo que la prueba puede proporcionar, pero cuando lo envío, recibo un error de límite de tiempo y mi respuesta no es aceptada.

¿Alguien tiene alguna sugerencia sobre cómo puedo mejorar mi algoritmo? Mientras escribía esta pregunta, pensé que en lugar de mi ciclo while (offset == 0 && offsetUpdated) podría usar un booleano para asegurarme de incrementar el desplazamiento en mi próxima [i] iteración. La confirmación de mi chang o cualquier sugerencia sería apreciada, también avíseme si necesito aclarar mi pregunta.

Answer 1

Bueno, tengo una solución de orden constante (al menos de orden k, donde k es el número de dígitos en el número)

Tomemos algunos ejemplos supongamos n = 17208

divide el número en dos partes desde el medio y escribe reversiblemente la parte más significativa en la menos significativa. es decir, 17271 si el número así generado es mayor que tu n , es tu palíndromo, si no solo aumenta el número central (pivote), es decir, obtienes 17371

Otros ejemplos

n = 17286 palidrome-attempt = 17271 (ya que es menor que n incremente el pivote, 2 en este caso) por lo que palidrome = 17371

n = 5684 palidrome1 = 5665 palidrome = 5775

n = 458322 palindrome = 458854

ahora supongamos que n = 1219901 palidrome1 = 1219121 incrementando el pivote hace que mi número sea más pequeño aquí, así que incremente el número pivote adyacente también 1220221

y esta lógica podría extenderse

Answer 2

Esto parece mucho código. ¿Has probado un enfoque muy ingenuo? Comprobar si algo es un palíndromo es realmente muy simple.

private boolean isPalindrome(int possiblePalindrome) {
String stringRepresentation = String.valueOf(possiblePalindrome);
if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
return true;
}
}

Ahora que tal vez no sea el código más eficiente, pero te da un punto de partida realmente simple:

private int nextLargestPalindrome(int fromNumber) {
for ( int i = fromNumber + 1; ; i++ ) {
if ( isPalindrome( i ) ) {
return i;
}
}
}

Ahora bien, si eso no es lo suficientemente rápido, puede usarlo como una implementación de referencia y trabajar para disminuir la complejidad algorítmica.

En realidad, debería haber una forma de tiempo constante (bueno, es lineal en el número de dígitos de la entrada) para encontrar el siguiente palíndromo más grande. Daré un algoritmo que asume que el número es un número par de dígitos de largo (pero puede extenderse a un número impar de dígitos).

1. Encuentre la representación decimal del número de entrada ("2133").
2. Divídalo en la mitad izquierda y la mitad derecha ("21", "33");
3. Compare el último dígito en la mitad izquierda y el primer dígito en la mitad derecha.
   a. Si la derecha es mayor que la izquierda, incremente la izquierda y pare. ("22")
   segundo. Si la derecha es menor que la izquierda, detente.
   do. Si la derecha es igual a la izquierda, repita el paso 3 con el penúltimo dígito a la izquierda y el segundo dígito a la derecha (y así sucesivamente).
4. Toma la mitad izquierda y agrega la mitad izquierda invertida. Ese es tu próximo palíndromo más grande. ("2222")

Aplicado a un número más complicado:

1. 1234567887654322
2. 12345678 87654322
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ equal
3. 12345678 87654322
^ ^ greater than, so increment the left
3. 12345679
4. 1234567997654321 answer

Esto parece un poco similar al algoritmo que describió, pero comienza en los dígitos internos y se mueve hacia el exterior.

Answer 3

Prueba esto

public static String genNextPalin(String base){
//check if it is 1 digit
if(base.length()==1){
if(Integer.parseInt(base)==9)
return "11";
else
return (Integer.parseInt(base)+1)+"";
}
boolean check = true;
//check if it is all 9s
for(char a: base.toCharArray()){
if(a!=''9'')
check = false;
}
if(check){
String num = "1";
for(int i=0; i<base.length()-1; i++)
num+="0";
num+="1";
return num;
}
boolean isBasePalin = isPalindrome(base);
int mid = base.length()/2;
if(isBasePalin){
//if base is palin and it is odd increase mid and return
if(base.length()%2==1){
BigInteger leftHalf = new BigInteger(base.substring(0,mid+1));
String newLeftHalf = leftHalf.add(BigInteger.ONE).toString();
String newPalin = genPalin2(newLeftHalf.substring(0,mid),newLeftHalf.charAt(mid));
return newPalin;
}
else{
BigInteger leftHalf = new BigInteger(base.substring(0,mid));
String newLeftHalf = leftHalf.add(BigInteger.ONE).toString();
String newPalin = genPalin(newLeftHalf.substring(0,mid));
return newPalin;
}
}
else{
if(base.length()%2==1){
BigInteger leftHalf = new BigInteger(base.substring(0,mid));
BigInteger rightHalf = new BigInteger(reverse(base.substring(mid+1,base.length())));
//check if leftHalf is greater than right half
if(leftHalf.compareTo(rightHalf)==1){
String newPalin = genPalin2(base.substring(0,mid),base.charAt(mid));
return newPalin;
}
else{
BigInteger leftHalfMid = new BigInteger(base.substring(0,mid+1));
String newLeftHalfMid = leftHalfMid.add(BigInteger.ONE).toString();
String newPalin = genPalin2(newLeftHalfMid.substring(0,mid),newLeftHalfMid.charAt(mid));
return newPalin;
}
}
else{
BigInteger leftHalf = new BigInteger(base.substring(0,mid));
BigInteger rightHalf = new BigInteger(reverse(base.substring(mid,base.length())));
//check if leftHalf is greater than right half
if(leftHalf.compareTo(rightHalf)==1){
return genPalin(base.substring(0,mid));
}
else{
BigInteger leftHalfMid = new BigInteger(base.substring(0,mid));
String newLeftHalfMid = leftHalfMid.add(BigInteger.ONE).toString();
return genPalin(newLeftHalfMid);
}
}
}
}
public static String genPalin(String base){
return base + new StringBuffer(base).reverse().toString();
}
public static String genPalin2(String base, char middle){
return base + middle +new StringBuffer(base).reverse().toString();
}
public static String reverse(String in){
return new StringBuffer(in).reverse().toString();
}
static boolean isPalindrome(String str) {
int n = str.length();
for( int i = 0; i < n/2; i++ )
if (str.charAt(i) != str.charAt(n-i-1))
return false;
return true;
}

Answer 4

Códigos simples y resultados de prueba:

class NextPalin
{
public static void main( String[] args )
{
try {
int[] a = {2, 23, 88, 234, 432, 464, 7887, 7657, 34567, 99874, 7779222, 2569981, 3346990, 229999, 2299999 };
for( int i=0; i<a.length; i++)
{
int add = findNextPalin(a[i]);
System.out.println( a[i] + " + " + add + " = " + (a[i]+add) );
}
}
catch( Exception e ){}
}
static int findNextPalin( int a ) throws Exception
{
if( a < 0 ) throw new Exception();
if( a < 10 ) return a;
int count = 0, reverse = 0, temp = a;
while( temp > 0 ){
reverse = reverse*10 + temp%10;
count++;
temp /= 10;
}
//compare ''half'' value
int halfcount = count/2;
int base = (int)Math.pow(10, halfcount );
int reverseHalfValue = reverse % base;
int currentHalfValue = a % base;
if( reverseHalfValue == currentHalfValue ) return 0;
if( reverseHalfValue > currentHalfValue ) return (reverseHalfValue - currentHalfValue);
if( (((a-currentHalfValue)/base)%10) == 9 ){
//cases like 12945 or 1995
int newValue = a-currentHalfValue + base*10;
int diff = findNextPalin(newValue);
return base*10 - currentHalfValue + diff;
}
else{
return (base - currentHalfValue + reverseHalfValue );
}
}
}
$ java NextPalin
2 + 2 = 4
23 + 9 = 32
88 + 0 = 88
234 + 8 = 242
432 + 2 = 434
464 + 0 = 464
7887 + 0 = 7887
7657 + 10 = 7667
34567 + 76 = 34643
99874 + 25 = 99899
7779222 + 555 = 7779777
2569981 + 9771 = 2579752
3346990 + 443 = 3347433
229999 + 9933 = 239932
2299999 + 9033 = 2309032

Answer 5

HI Aquí hay otro algoritmo simple que usa Python,

 def is_palindrome(n):
if len(n) <= 1:
return False
else:
m = len(n)/2
for i in range(m):
j = i + 1
if n[i] != n[-j]:
return False
return True
def next_palindrome(n):
if not n:
return False
else:
if is_palindrome(n) is True:
return n
else:
return next_palindrome(str(int(n)+1))
print next_palindrome(''1000010'')

Answer 6

Aquí está mi código en java. Toda la idea es de aquí http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

import java.util.Scanner;

clase pública Principal {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter number of tests: ");
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
System.out.println("Enter number: ");
String numberToProcess = sc.next(); // ne proveravam dal su brojevi
nextSmallestPalindrom(numberToProcess);
}
}
private static void nextSmallestPalindrom(String numberToProcess) {
int i, j;
int length = numberToProcess.length();
int[] numberAsIntArray = new int[length];
for (int k = 0; k < length; k++)
numberAsIntArray[k] = Integer.parseInt(String
.valueOf(numberToProcess.charAt(k)));
numberToProcess = null;
boolean all9 = true;
for (int k = 0; k < length; k++) {
if (numberAsIntArray[k] != 9) {
all9 = false;
break;
}
}
// case 1, sve 9ke
if (all9) {
whenAll9(length);
return;
}
int mid = length / 2;
if (length % 2 == 0) {
i = mid - 1;
j = mid;
} else {
i = mid - 1;
j = mid + 1;
}
while (i >= 0 && numberAsIntArray[i] == numberAsIntArray[j]) {
i--;
j++;
}
// case 2 already polindrom
if (i == -1) {
if (length % 2 == 0) {
i = mid - 1;
j = mid;
} else {
i = mid;
j = i;
}
addOneToMiddleWithCarry(numberAsIntArray, i, j, true);
} else {
// case 3 not polindrom
if (numberAsIntArray[i] > numberAsIntArray[j]) { // 3.1)
while (i >= 0) {
numberAsIntArray[j] = numberAsIntArray[i];
i--;
j++;
}
for (int k = 0; k < numberAsIntArray.length; k++)
System.out.print(numberAsIntArray[k]);
System.out.println();
} else { // 3.2 like case 2
if (length % 2 == 0) {
i = mid - 1;
j = mid;
} else {
i = mid;
j = i;
}
addOneToMiddleWithCarry(numberAsIntArray, i, j, false);
}
}
}
private static void whenAll9(int length) {
for (int i = 0; i <= length; i++) {
if (i == 0 || i == length)
System.out.print(''1'');
else
System.out.print(''0'');
}
}
private static void addOneToMiddleWithCarry(int[] numberAsIntArray, int i,
int j, boolean palindrom) {
numberAsIntArray[i]++;
numberAsIntArray[j] = numberAsIntArray[i];
while (numberAsIntArray[i] == 10) {
numberAsIntArray[i] = 0;
numberAsIntArray[j] = numberAsIntArray[i];
i--;
j++;
numberAsIntArray[i]++;
numberAsIntArray[j] = numberAsIntArray[i];
}
if (!palindrom)
while (i >= 0) {
numberAsIntArray[j] = numberAsIntArray[i];
i--;
j++;
}
for (int k = 0; k < numberAsIntArray.length; k++)
System.out.print(numberAsIntArray[k]);
System.out.println();
}

}

Answer 7

public class NextPalindrome
{
int rev, temp;
int printNextPalindrome(int n)
{
int num = n;
for (int i = num+1; i >= num; i++)
{
temp = i;
rev = 0;
while (temp != 0)
{
int remainder = temp % 10;
rev = rev * 10 + remainder;
temp = temp / 10;
}
if (rev == i)
{
break;
}
}
return rev;
}
public static void main(String args[])
{
NextPalindrome np = new NextPalindrome();
int nxtpalin = np.printNextPalindrome(11);
System.out.println(nxtpalin);
}
}

Answer 8

He escrito comentarios para aclarar qué está haciendo cada paso en este código python.

Una cosa que debe tenerse en cuenta es que la entrada puede ser muy grande y no podemos simplemente realizar operaciones enteras sobre ella. Entonces, tomar la entrada como una cadena y luego manipularla sería mucho más fácil.

tests = int(input())
results = []
for i in range(0, tests):
pal = input().strip()
palen = len(pal)
mid = int(palen/2)
if palen % 2 != 0:
if mid == 0: # if the number is of single digit e.g. next palindrome for 5 is 6
ipal = int(pal)
if ipal < 9:
results.append(int(pal) + 1)
else:
results.append(11) # for 9 next palindrome will be 11
else:
pal = list(pal)
pl = l = mid - 1
pr = r = mid + 1
flag = ''n'' # represents left and right half of input string are same
while pl >= 0:
if pal[pl] > pal[pr]:
flag = ''r'' # 123483489 in this case pal[pl] = 4 and pal[pr] = 3 so we just need to copy left half in right half
break # 123484321 will be the answer
elif pal[pl] < pal[pr]:
flag = ''m'' # 123487489 in this case pal[pl] = 4 and pal[pr] = 9 so copying left half in right half will make number smaller
break # in this case we need to take left half increment by 1 and the copy in right half 123494321 will be the anwere
else:
pl = pl -1
pr = pr + 1
if flag == ''m'' or flag == ''n'': # increment left half by one and copy in right half
if pal[mid] != ''9'': # if mid element is < 9 the we can simply increment the mid number only and copy left in right half
pal[mid] = str(int(pal[mid]) + 1)
while r < palen:
pal[r] = pal[l]
r = r + 1
l = l - 1
results.append(''''.join(pal))
else: # if mid element is 9 this will effect entire left half because of carry
pal[mid] = ''0'' # we need to take care of large inputs so we can not just directly add 1 in left half
pl = l
while pal[l] == ''9'':
pal[l] = ''0''
l = l - 1
if l >= 0:
pal[l] = str(int(pal[l]) + 1)
while r < palen:
pal[r] = pal[pl]
r = r + 1
pl = pl - 1
if l < 0:
pal[0] = ''1''
pal[palen - 1] = ''01''
results.append(''''.join(pal))
else:
while r < palen: # when flag is ''r''
pal[r] = pal[l]
r = r + 1
l = l - 1
results.append(''''.join(pal))
else: # even length almost similar concept here with flags having similar significance as in case of odd length input
pal = list(pal)
pr = r = mid
pl = l = mid - 1
flag = ''n''
while pl >= 0:
if pal[pl] > pal[pr]:
flag = ''r''
break
elif pal[pl] < pal[pr]:
flag = ''m''
break
else:
pl = pl -1
pr = pr + 1
if flag == ''r'':
while r < palen:
pal[r] = pal[l]
r = r + 1
l = l - 1
results.append(''''.join(pal))
else:
if pal[l] != ''9'':
pal[l] = str(int(pal[l]) + 1)
while r < palen:
pal[r] = pal[l]
r = r + 1
l = l - 1
results.append(''''.join(pal))
else:
pal[mid] = ''0''
pl = l
while pal[l] == ''9'':
pal[l] = ''0''
l = l - 1
if l >= 0:
pal[l] = str(int(pal[l]) + 1)
while r < palen:
pal[r] = pal[pl]
r = r + 1
pl = pl - 1
if l < 0:
pal[0] = ''1''
pal[palen - 1] = ''01''
results.append(''''.join(pal))
for xx in results:
print(xx) 

Answer 9

El siguiente código encuentra el siguiente número de Palandrome para un número-

public class TestNextPalindrome {
public static void main(String[] args) {
int number1 = 45312;
int number2 = 12345;
int number3 = 12945;
int number4 = 4531;
int number5 = 1459;
int number6 = 1997;
System.out.print("For the number " + number1);
getNextPalindrome(number1);
System.out.print("For the number " + number2);
getNextPalindrome(number2);
System.out.print("For the number " + number3);
getNextPalindrome(number3);
System.out.print("For the number " + number4);
getNextPalindrome(number4);
System.out.print("For the number " + number5);
getNextPalindrome(number5);
System.out.print("For the number " + number6);
getNextPalindrome(number6);
}
private static void getNextPalindrome(int number) {
if (isSizeEven(number)) {
getNextPalindromeForEvenLengthNumbers(number);
}
else {
getNextPalindromeForOddLengthNumbers(number);
}
}
private static boolean isSizeEven(int number) {
if (String.valueOf(number).length() % 2 == 0)
return true;
return false;
}
private static void getNextPalindromeForEvenLengthNumbers(int number) {
StringBuilder testPalindromeString = new StringBuilder();
testPalindromeString.append(number);
StringBuilder convertTopalindrome = new StringBuilder();
convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2));
convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2,
testPalindromeString.length()).reverse());
//if the palindrome is greater than the original number
if (Integer.parseInt(convertTopalindrome.toString()) > number) {
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
//get the middle elements in case of even numbers
String middleElements =
convertTopalindrome.substring(convertTopalindrome.length() / 2 - 1,
convertTopalindrome.length() / 2 + 1);
int middleElementsInt = Integer.valueOf(middleElements);
//we are going to increment the middle elements by 1 so check if after this the value is not greater than 99.
if (middleElementsInt + 11 < 99) {
convertTopalindrome.replace(convertTopalindrome.length() / 2 - 1,
convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementsInt + 11));
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
String numberTillMiddleElement =
convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1);
int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement);
convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1,
String.valueOf(numberTillMiddleElementInt + 1));
getNextPalindrome(Integer.valueOf(convertTopalindrome.toString()));
}
}
}
private static void getNextPalindromeForOddLengthNumbers(int number) {
StringBuilder testPalindromeString = new StringBuilder();
testPalindromeString.append(number);
StringBuilder convertTopalindrome = new StringBuilder();
convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2 + 1));
convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2,
testPalindromeString.length()).reverse());
//if the palindrome is greater than the original number
if (Integer.parseInt(convertTopalindrome.toString()) > number) {
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
char middleElement = convertTopalindrome.charAt(convertTopalindrome.length() / 2);
int middleElementInt = Character.getNumericValue(middleElement);
//we are going to increment the middle element by 1 so check if after this the value is not greater than 9.
if (middleElementInt < 9) {
convertTopalindrome.replace(convertTopalindrome.length() / 2,
convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementInt + 1));
System.out.println(" the next palindrome is " + convertTopalindrome);
}
else {
String numberTillMiddleElement =
convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1);
int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement);
convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1,
String.valueOf(numberTillMiddleElementInt + 1));
getNextPalindrome(Integer.valueOf(convertTopalindrome.toString()));
}
}
}
}

La explicación del código se puede encontrar aquí: Encontrar Next Palindrome usando Java

Answer 10

No hay ninguna razón para juguetear con dígitos individuales cuando la única operación necesaria es una simple adición. El siguiente código se basa en la respuesta de Raks .

El código enfatiza la simplicidad sobre la velocidad de ejecución, intencionalmente.

import static org.junit.Assert.assertEquals;
import java.math.BigInteger;
import org.junit.Test;
public class NextPalindromeTest {
public static String nextPalindrome(String num) {
int len = num.length();
String left = num.substring(0, len / 2);
String middle = num.substring(len / 2, len - len / 2);
String right = num.substring(len - len / 2);
if (right.compareTo(reverse(left)) < 0)
return left + middle + reverse(left);
String next = new BigInteger(left + middle).add(BigInteger.ONE).toString();
return next.substring(0, left.length() + middle.length())
+ reverse(next).substring(middle.length());
}
private static String reverse(String s) {
return new StringBuilder(s).reverse().toString();
}
@Test
public void testNextPalindrome() {
assertEquals("5", nextPalindrome("4"));
assertEquals("11", nextPalindrome("9"));
assertEquals("22", nextPalindrome("15"));
assertEquals("101", nextPalindrome("99"));
assertEquals("151", nextPalindrome("149"));
assertEquals("123454321", nextPalindrome("123450000"));
assertEquals("123464321", nextPalindrome("123454322"));
}
}