Finding closest palindrome to string

Question

I am trying to write a python program to find the closest palindrome to a word. I can add a letter to any part of the string, remove a letter from any part of the string, or change a letter in any part of a string. I have been looking at using the levenshtein distance to find the minimum number of edits needed between two words in the post Edit Distance in Python. But I am not sure how to programmatically find the palindrome that requires the smallest number of edits. Some examples for what I am trying to achieve:

palindrome('hello') = 'ollo'
#you can remove the h and then turn the e into an o, giving a palindrome in 2 steps
levenshtein('hello',palindrome('hello')) = 2

palindrome('test') = 'tet'
#you can remove the s to get a palindrome
levenshtein('test',palindrome('test')) = 1

palindrome('tart') = 'trart'
#adding an r or removing the r produces a palindrome, but both solutions only require 1 edit so either would be acceptable.
levenshtein('tart',palindrome('tart')) = 1

I was able to use the levenshtein code from the linked post to find the distance between two strings. I need help writing a palindrome() function that takes a string and returns the closest palindrome to that string.

In the worst case, you should be able to construct a palindrome from any one-letter substring of a string. Perhaps start there, iterating between letters in an original string *o*, to divide *o* into two pieces *o1* and *o2*, either having a minimum length of two characters. Then do a sequence alignment between the two fragments where you assign your penalty (edit distance) to insertion or deletion. Compare edit distances and types with the lengths of substrings *o1* and *o2* to decide how to construct the palindrome. — Alex Reynolds, Mar 18 '17 at 22:32
Possible duplicate of [how to convert a string into a palindrome with minimum number of operations?](http://stackoverflow.com/questions/4737791/how-to-convert-a-string-into-a-palindrome-with-minimum-number-of-operations) — Chris Martin, Mar 18 '17 at 22:34

Junuxx · Accepted Answer · 2017-03-18T23:40:50.397

Well here's my DFS implementation. It only searches up to a distance of word length-2, because past that it becomes kind of trivial (drop all but one letter, change every letter to the same).

It finds all palindromes up to that distance limit, and sorts them by distance.

import time
word = "hello"
visited_cost = {}       # to keep track of non-palindromes we've considered
palindrome_cost = {}    # to store actual palindromes we've found


def find_palindrome(w, dist=0 ):
    # Don't go on forever
    if len(w) == 0 or len(w) > len(word) + 2 or dist > len(word) - 2:
        return []

    # Don't retry potential palindromes that we've tried before
    global visited_cost
    if w in visited_cost:
        if dist >= visited_cost[w]:
            return []
    visited_cost[w] = dist

    # check if we've found a palindrome
    if (reverse(w)) == w:
        if w in palindrome_cost:
            palindrome_cost[w] = min(palindrome_cost[w], dist)
        else:
            palindrome_cost[w] = dist
        return [w]

    palindromes = []
    if len(w) > 1:
        for x in drop_one(w):
            palindromes += find_palindrome(x, dist+1)
        for x in add_one(w):
            palindromes += find_palindrome(x, dist+1)
        for x in change_one(w):
            palindromes += find_palindrome(x, dist+1)
        return palindromes


# For a word w, gives all possible words obtained by dropping one letter
def drop_one(w):
    return [w[:i]+w[i+1:] for i in range(len(w))]


# For a word w, gives all possible words obtained by inserting a capital X
# at any position in the word. Of course "X" could be any letter
def add_one(w):
    return [w[:i]+"X"+ w[i:] for i in range(len(w))]


# For a word w, gives all possible words obtained by changing one letter 
# to another letter occurring in the word
def change_one(w):
    return [w[:i] +j +  w[i + 1:] for i in range(len(w)) for j in w]


def reverse(s):
    return "".join(reversed(s))

t0 = time.time()
results = set(find_palindrome(word))
s = sorted(results, key = lambda x: palindrome_cost[x])

for x in s:
    print x, palindrome_cost[x]
print "Found %i palindromes based on '%s' in %.3f seconds" %\
       (len(results), word, time.time() - t0)

Output:

ollo 2
olllo 2
elle 2
heleh 2
hllh 2
oeleo 2
hlllh 2
[...]
Found 46 palindromes based on 'hello' in 0.065 seconds

Thanks for your help. I am trying to implement this function inside of a while loop that reads in words from the command line and getting an error on the variable word not being defined. Do the last lines starting with t0 = time.time() have to be after the function definintion? — Brent Ferrier, Mar 19 '17 at 01:01

Finding closest palindrome to string

1 Answers1