fork(4) download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. static String shortestPalindrome(String s) {
  11. 	return recShortestPalindrome(s, s.length()>>1, 0);
  12. }
  13.  
  14. static String recShortestPalindrome(String s, int mid, int add) {
  15. 	// AABBA[X]
  16. 	int fakeLen = s.length() + add;
  17. 	for (int i = 0; i < mid; i++) {
  18. 		char c1 = s.charAt(i);
  19. 		int p1 = fakeLen - 1 - i;
  20.  
  21. 		if (p1 < s.length()) {
  22. 			char c2 = s.charAt(p1);
  23.  
  24. 			if (c2 != c1) {
  25. 				return recShortestPalindrome(s, mid+1, add+1);
  26. 			}
  27. 		}
  28. 	}
  29.  
  30. 	// found a pattern that works
  31. 	String h1 = s.substring(0, mid);
  32. 	String h2 = new StringBuilder(h1).reverse().toString();
  33.  
  34. 	String ret = h1+h2;
  35.  
  36. 	int midPoint = ret.length()/2;
  37.  
  38. 	if (ret.length()%2 == 0 && ret.length() >= 4) {
  39. 		char c1 = ret.charAt(midPoint);
  40. 		char c2 = ret.charAt(midPoint-1);
  41.  
  42. 		if (c1 == c2) {
  43. 			return ret.substring(0, midPoint) + ret.substring(midPoint+1, ret.length());
  44. 		}
  45. 	}
  46.  
  47. 	return h1+h2;
  48. }
  49.  
  50. 	public static void main (String[] args) throws java.lang.Exception
  51. 	{
  52. 		// your code goes here
  53. 		System.out.println(shortestPalindrome("racec"));
  54. 	}
  55. }
Success #stdin #stdout 0.09s 320320KB
comments (?)
stdin 
Standard input is empty
stdout 
racecar
https://ideone.com/tawjmG
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!