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
Follow me on Twitter: @john_canessa