Palindromes and Longest Common Subsequence

1 minute read

Longest Common Subsequence and Palindromes

A solution for finding Palindromes is using the Longest Common Subsequence(LCS) algorithm on the string and its reversed version. In this example I implement the LCS algorithm with dynamic programming and return all the longest common subsequences Here is an Dynamic Programming implementation of the Longest Common Subsequence algorithm.

def findAllLCS(s1,s2):
    n = len(s1)
    m = len(s2)
    #For the length of longsest common substring
    c = [[0 for _ in range(m+1)] for _ in range(n+1)]
    #Path leading the longest length
    p = [[0 for _ in range(m)] for _ in range(n)] 
    for i in range(n):
        for j in range(m):
            if s1[i] == s2[j]:
                c[i+1][j+1] = c[i][j]+1
            elif c[i][j+1] > c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
                p[i][j] = 1
            elif c[i][j+1] < c[i+1][j]:
                c[i+1][j+1] = c[i+1][j]
                p[i][j] = -1
                c[i+1][j+1] = c[i+1][j]
                p[i][j] = 2
    return list(allstrs)
def getLCS(s1,p,allstrs,n,m,cur_s):
    while n>=0 and m>=0:
        if p[n][m] == 0:
            n -= 1
            m -= 1
        elif p[n][m] == 2:
            m -= 1
        elif p[n][m] == 1:
        else: #p[n][m] == -1

Test Cases

An important note is, not all longest LCS’s are palidrome. But there is at least one in the set of longest subsequences.


for s in strs:
    print findAllLCS(s,s[::-1])
['EYE', 'HYE', 'EOE', 'HYH', 'EYH', 'EHE', 'HEH']