0

I currently have the following implementation that handles finding the shortest palindrome with a given string by inserting the minimum number of characters, but only handling character insertions at the front to create the shortest palindrome.

But with the following implementation or if there's any better out there, how can I do so where the characters can be inserted at any point(s) in the string to make it a palindrome?

Will accept and upvote the answer. Thank you

public class Answer {
    public String findShortestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        int i = len - 1;
        for (; i >= 0; --i) {
            if (stringIsPalindrome(s, 0, i)) {
                break;
            }
        }

        StringBuilder sb = new StringBuilder(s.substring(i + 1));
        sb.reverse().append(s);
        return sb.toString();
    }

    public boolean stringIsPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

DIFFERENCE Looking for shortest palindrome that handles insertion in any point in the string.

Jo Ko
  • 7,225
  • 15
  • 62
  • 120
  • 3
    This sounds like homework. – Bálint Nov 16 '16 at 08:53
  • Possible duplicate of [Convert string to palindrome string with minimum insertions](http://stackoverflow.com/questions/10729282/convert-string-to-palindrome-string-with-minimum-insertions) – Paul Hankin Nov 16 '16 at 13:24

2 Answers2

1

You could try this solution. This should works!

public boolean stringIsPalindrome(String s, int start, int end) {

    String str1 = s.substring(0,Math.floor((end-start)/2));
    String str2 = s.substring(Math.floor((end-start)/2),end);
    str2 = reverseString(str2);
    return str1.equals(str2);
}

public String reverseString(String s) {
            //YOUR REVERSE STRING METHOD
    }
dariodip
  • 230
  • 3
  • 13
  • 2
    I don't think this is what Jo was asking for. Also your stringIsPalindrome is actually slower than his original method, since it creates a extra string, reverses one of them and then compares them. – baseballlover723 Nov 16 '16 at 09:07
  • I'm sorry! I just propose a possible solution – dariodip Nov 16 '16 at 11:16
0

You can implement the following kinda brute force algorithm:

  1. If the input string is empty or consists of one element return the input
  2. If first character of the string equals last one then apply the procedure to the input string without first and last items

  3. If first is not the same with last then you have two options: 

    left = last + palindromed(input without last) + last  or
right = first + palindromed(input without first) + first

    so on this step you select the shortest solution

Nyavro
  • 8,806
  • 2
  • 26
  • 33
  • Before I accept the answer and upvote, for clarification could you show an example with what I've implemented so far? Thank you – Jo Ko Nov 16 '16 at 13:43