CODEWITHSUNDEEP
javaalgorithmdynamic-programmingpalindrome
Jo Ko
Jo Ko

Reputation: 7575

Java: How to create the shortest palindrome of a string by inserting the minimum number of characters?

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.

Upvotes: 0

Views: 1533

Answers (2)

Nyavro
Nyavro

Reputation: 8866

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

Upvotes: 0

dariodip
dariodip

Reputation: 228

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
    }

Upvotes: 1

Related Questions