力扣1312. 让字符串成为回文串的最少插入次数

 动态规划

• 思路：
  • 通过插入字符构造回文串，要想插入次数最少，可以将字符串 s 的逆序 s' 进行比较找出最长公共子序列；
  • 可以先分析，字符串 s 通过插入得到回文串 ps，其中间的字符应该不会变化：

    • 若 s' 的长度为奇数，那么它的回文中心为单个字符 c。例如当 s' = "adgda" 时，它的回文中心为单个字符 "g"。我们可以断定，回文中心 c 一定是原字符串 s 中的字符，否则如果 c 是通过操作添加的字符，那么我们可以舍弃这一步操作，此时 s' 成为长度为偶数的字符串，并且它仍是回文串（在例子中，即 "adgda" -> "adda"）

    • 若 s' 的长度为偶数，那么它的回文中心为两个字符 cc，例如当 s' = "adggda" 时，它的回文中心为两个字符 "gg"。我们同样可以断定，回文中心 cc 一定是原字符串中的两个字符，否则如果 cc 中有至少一个是通过操作添加的字符，那么我们可以舍弃这些操作，此时 s' 成为长度为偶数（舍弃一次操作）或奇数（舍弃两次操作）的字符串，并且它仍是回文串（在例子中，即 "adggda" -> "adgda" 或 "adggda" -> "adda"）。

  • 可以通过原字符串与逆序字符串进行“并集”构建回文字符串，可以假设字符串 s 分成三部分 s(l) c s​​​(r)，则其逆序字符串 s(r) c s(l)；

  • 如果构建之后的回文字符串看作一块板子，原串和逆串像两个“缺了孔”的两块板子叠在一起，补上“缺的孔”就构成了回文串，一样的是公共子串；

  • 那么需要补上的“孔”的个数为原串长度减去公共子串长度；

  • 综上，问题回到求取两个字符串的最长公共子串，参考 力扣1143. 最长公共子序列

class Solution {
public:int minInsertions(string s) {int n = s.size();std::string invs(s.rbegin(), s.rend());std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1));for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);if (s[i - 1] == invs[j - 1]) {dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + 1);}}}return n - dp[n][n];}
};

————————————————————————————————————