Clever Geek Handbook

Taming the dynamics in the palindromes problem

I have not been a student for a long time, but in my free time I study materials on Computer Science. I enjoy learning and sharing. Recently I came across a curious problem in the famous textbook "Algorithms: Construction and Analysis". In this article, I will demonstrate the principles of dynamic programming using this task. It is interesting, not very complicated, and you don't need to write any additional data structures or libraries to solve it. The wording fits into one sentence:



Find the longest palindromic subsequence in a word of wlength n.



Who cares, please, under cat.



Don't confuse the concepts of "substring" and "sequence". The first includes only neighboring letters, and the second can be composed of letters arbitrarily far from each other. For example, in the word "mathematics" subsequences will "poppy" ( m ate m atm to a), the "attack" (m atm cm and ti ka ) or a "label" ( m atm e ma t and ka). "Palindromic" means that the subsequence must be read equally from left-to-right and right-to-left. A sequence of one letter will also be palindromic, although this is a degenerate case. It is clear that there can be many such palidnromic subsequences in one line. We are interested in the longest one. If wthe palindrome itself, then the answer will be the whole string. Otherwise, the answer must be looked for somehow, for example, in the word "brace" the answer will be "oooo".



It sounds simple, let's get down to the analysis. First, let's try to solve "head-on". How many subsequences does a word have in total n? It's easy to calculate. When composing a subsequence, we either take the ith letter or not. It turns out that each subsequence can be put in one-to-one correspondence with a binary number with nbits (possibly starting with zeros). Since there are only such numbers 2^n, there will be one less subsequences, because we do not consider empty. It turns out that the search space grows exponentially with growth n. This alignment immediately makes it clear that there is no point in making a head-on decision. No one wants a program that, even on relatively small lines (withn = 1000) will be executed for centuries. The whole point of computers is that they cope with mechanical tasks much faster than we do, and if a computer runs a program longer than a person, then why was it worth the "fence"?



Small digression



, - ? , , ? , (, ) , . ? — , . , , , - . , , -. , , .



— "" , — , — , . .. "time-space trade-off" ( ), "" , . , , . " " , . -. "" "" "", "", . "" - , . , , . , . , - . — .



, . , , . (P vs. NP). ( " "), , .



.





. , . , — , . (), . " " , . , . . "" . , .. , .. :



  • .
  • , .. .


  • .


? , f . , f (.. "").



. w , . , ? , , . , . , , . , - .



, , . palindrome[i, j] w[i, j]. palindrome[1, n]. . , , palindrome[1, n]. ? , w[1, n-1], w[2, n], w[2, n-1]. w , w[1] + palindrome[2, n-1] + w[n]. :



  1. palindrome[j, i] = , j > i
  2. palindrome[i, i] = w[i].
  3. palindrome[i, j] = w[i] + palindrome[i + 1, j - 1] + w[j] w[i] = w[j]
  4. palindrome[i, j] = max{palindrome[i+1, j], palindrome[i, j-1], palindrome[i+1, j-1]}

    . , Python - :


def solve(s):
    palindromes = [['' for i in range(len(s))] for j in range(len(s))]
    n = len(s) - 1
    result = solve_memoized_rec(s, palindromes, 0, n)
    return result

def solve_memoized_rec(s, palindromes, i, j):
    if palindromes[i][j]:
        return palindromes[i][j]
    else:
        if i > j:
            solution = ''
        elif i == j:
            solution = s[i]
        elif s[i] == s[j]:
            prev = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = s[i] + prev + s[j]
        else:
            from_left = solve_memoized_rec(s, palindromes, i + 1, j)
            from_right = solve_memoized_rec(s, palindromes, i, j - 1)
            both = solve_memoized_rec(s, palindromes, i + 1, j - 1)
            solution = max(from_left, from_right, both, key=len)
        palindromes[i][j] = solution
        return solution


solve_memoized_rec palindromes, . , , . , - ( ). , , , . — . — , n (, ). , .. off-by-one error.



" ", " " palindromes. "". , "" palindromes[1, n].



:



def solve_iterative(s):
    n = len(s)
    palindromes = [['' for i in range(n)] for j in range(n)]
    for k in range(1, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if i == j:
                solution = s[i]
            elif s[i] == s[j]:
                solution = s[i] + palindromes[i + 1][j - 1] + s[j]
            else:
                solution = max(palindromes[i + 1][j], palindromes[i][j - 1], palindromes[i + 1][j - 1], key=len)
            palindromes[i][j] = solution
    return palindromes[0][n - 1]


, , i > j. , n^2.





, , . , !



I welcome any feedback both on the content of the article and on the code. My telegram: @outofbound



More articles:


All Articles