Palindrome Completion

Completing a string to a palindrome with the minimal number of characters.

For the leetcode daily ‘shortest palindrome’ question.

Analysis

It is relatively easy to find a trivial solution - first, check is the entire string is a palindrome, then the n-1 substring, and so on. Whenever a palindrome is found, reverse the remainder of the string and throw it in front.

Solutions

The Trivial Solution

# start snippet solution_trivial
class SolutionTrivial:

    def shortestPalindrome(self, s: str):

        n = len(s)
        if n <= 1:
            return s

        best_init = 0
        for k in range(n, 0, -1):
            if (t := s[0:k]) == t[::-1]:
                best_init = k
                break

        mantisa = s[best_init:]
        return mantisa[::-1] + s

    # stop snippet trivial