Minimum insertion to form palindrome

题目描述

Given a string, find the minimum number of characters to be inserted to convert it to palindrome.

Before we go further, let us understand with few examples:

  • ab: Number of insertions required is 1. bab
  • aa: Number of insertions required is 0. aa
  • abcd: Number of insertions required is 3. dcbabcd
  • abcda: Number of insertions required is 2. adcbcda which is same as number of insertions in the substring bcd(Why?).
  • abcde: Number of insertions required is 4. edcbabcde

解题方法

输入s[start:end]，可以有三种sub-problem可以相关(只insert到头部或者尾部)

  • min_insert(s[start+1:end-1])
  • min_insert(s[start:end-1])
  • min_insert(s[start+1:end])

recursion

if s[start] == s[end-1]:
    result = min(min_insert(s[start+1:end-1]))
else:
    result = min(min_insert(s[start:end-1]), # insert在尾部
                min_insert(s[start+1:end])
                ) + 1 # insert在头部

可以得到一个recursion的解法

DP

Recursion has some duplicate calculations, so 我们可以往DP的方向想

                      abcde
            /       |      \
           /        |        \
           bcde         abcd       bcd  <- case 3 is discarded as str[l] != str[h]
       /   |   \       /   |   \
      /    |    \     /    |    \
     cde   bcd  cd   bcd abc bc
   / | \  / | \ /|\ / | \
de cd d cd bc c………………….

可以想到用dp[i][j]表示s[i][j]的min insert, 但是这里要注意的是这个dp table的 fill的顺序。

  • 单个字母的min insert都是0
  • 所以我们应该从两个字母的substr开始，然后三个字母的，四个字母的。。。

  • 所以这个类似window的移动过程要在for loop里体现出来

  • Time complexity: 'O(N^2)'

  • Auxiliary Space: 'O(N^2)'

　另一个ＤＰ的方法

利用找ＬＣＳ(longest common substring)的方法，找出s和reversed s的ＬＣＳ

Solution

Reference