本文共 426 字，大约阅读时间需要 1 分钟。

问题A：

给定一个字符串，任意位置可以添加新字符，则最少添加几个变为回文串：

dp，时间O(N*N)

维护二维表，dp[i][j] 表示 区间[i…j]所需最少字符。

转移方程：dp[i][j] = dp[i+1][j-1] or dp[i][j] = min{dp[i+1][j], dp[i][j-1]} + 1

---

问题B：

给定一个字符串str，再给定一个回文子串strpls，则在添加元素最少时，给出str的回文串。

剥洋葱，时间O(N)

L，R从str外层找strpls最外的元素，然后处理L，R之外元素，然后依次往内层递归。

---

问题C：

给定一串括号，给出最长合法子串。

例如，“（）（（）（）（”，返回4

dp，时间O(N)

dp[i]表示必须以 i 结尾的最长合法串长度。

所以循环时考虑，i - dp[i] - 1位置和i-1位置即可。 有种特殊情况，需要处理， 即"()(())"的情况，当找到“(())”后，需要把之前的“()”合并。

---

转载地址：http://mbwji.baihongyu.com/