Google – Minimum Add to Make a Palindrome
Given a string, return the minimum number of characters to add to make the string a Palindrome
[Analysis]
和leetcode214 shortest palindrome有点类似，不过这题可以算shortest palindrome的一个follow up。因为这道题可以在任何一个位置插入character，而shortest palindrome只能在两端append。
[Solution]
Dynamic Programming. 跟longest palindrome substring的DP解法一样。
lookup[i][j]表示minimum add to make substring from i to j a palindrome
if s.charAt(i) == s.charAt(j)
lookup[i][j] = lookup[i + 1][j – 1]
else
lookup[i][j] = Math.min(lookup[i][j – 1], lookup[i + 1][j]) + 1
而对于Leetcode214 shortest palindrome这样在两段append来make palindrome的，除了从mid开始往一边扫的方法之外。还有一种O(n) KMP的做法。比如leetcode这道:
str = s + '#' + reversed_s
然后用kmp找longest prefix&suffix的方法找到str的longest prefix & suffix. Reverse一下s的剩余部分就是要往左边append的字符串。
如果是从右边append，那str = reversed_s + '#' + s就可以了。
[Note]
注意中间的'#'必不可少. 不然会出bug。
比如aabba这个case, 如果不加'#'，str = aabbaabbaa, 这样longest prefix & suffix就会变成aabbaa，超出了原来string的长度。
加个'#'之后就可以保证longset prefix & suffix的length小于等于s.length()
Read full article from Google – Minimum Add to Make a Palindrome
No comments:
Post a Comment