Minimal Palindrome

Given a string generate the minimal palindrome. For example:

abc -> abcba

abb -> abba

abccc -> abcccba

I decided to use a stack for this solution. It can also be easily developed with string indices.

The output of the Eclipse console follows:

main <<< str [- to exit]: abc

main <<< str ==>abc<== pal ==>abcba<==

main <<< str [- to exit]: abb

main <<< str ==>abb<== pal ==>abba<==

main <<< str [- to exit]: abccc

main <<< str ==>abccc<== pal ==>abcccba<==

main <<< str [- to exit]: –

The associated Java code for the solution follows:

import java.util.Scanner;

import java.util.Stack;

public class Solution {

/**

* Generate the minimal palindrome using the specified string.

*/

static String minPalindrome(String str) {

// **** push characters into stack ****

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < str.length(); i++) {

stack.push(str.charAt(i));

}

// **** pop characters from stack ****

String pal = str;

while (!stack.isEmpty()) {

char c = stack.pop();

if (c != pal.charAt(pal.length() – 1)) {

pal += Character.toString(c);

}

}

// **** ****

return pal;

}

/**

* Test code.

* @param args

*/

public static void main(String[] args) {

// **** ****

boolean done = false;

// **** ****

Scanner sc = new Scanner(System.in);

// **** ****

do {

// **** ****

System.out.print(“main <<< str [- to exit]: “);

String str = sc.nextLine();

// **** ****

if (str.equals(“-“)) {

done = true;

}

else {

// **** generate palindrome ****

String pal = minPalindrome(str);

// **** display palindrome ****

System.out.println(“main <<< str ==>” + str + “<== pal ==>” + pal + “<==”);

}

} while (!done);

// **** close scanner ****

sc.close();

}

}

If you have comments or questions regarding this or any other entry in this blog please let me know. I will not use your name unless you explicitly allow me to do so.

 

John

john.canessa@gmail.com

Follow me on Twitter: @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *