知识点

知识点
1. 经典回文串问题
  1. 最长回文子串问题
    
    解题思路：
    
    寻找回文子串的问题，一般都是使用从中间进行双指针判断的方法进行的。
    
    因此对于该题型，只要遍历字符串，找到以字符串中每个字符为中心左右探路寻找的回文串，哪个最长即可。
    
    因为回文串的字符可能为奇数，也可能为偶数，因此要同时处理奇数的情况和偶数的情况。
  2. 最长回文子序列问题
    
    解题思路：
    
    一旦涉及到子序列和最值，那几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。
    
    该题目中，我们定义dp数组为：在子串s[i..j]中，最长回文子序列的长度为dp[i][j]。
    
    明确一下 base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是dp[i][j] = 1,(i == j)
    
    然后，根据数学归纳法来找状态转移方程。具体来说，如果我们想求dp[i][j]，假设你知道了子问题dp[i+1][j-1]的结果，如何推导出dp[i][j]。这取决于s[i]和s[j]的字符，如果它俩相等，那么它俩加上s[i+1..j-1]中的最长回文子序列就是s[i..j]的最长回文子序列；如果它俩不相等，说明它俩不可能同时出现在s[i..j]的最长回文子序列中，那么把它俩分别加入s[i+1..j-1]中，看看哪个子串产生的回文子序列更长即可。
    
    至此，状态转移方程就写出来了：
```
 if (s[i] == s[j]) {
     dp[i][j] = dp[i+1][j-1] + 2;
 } else {
     dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
 }
```
    最后，根据base case和状态转移方程，选择遍历方式即可。我们选择从下到上，从左到右遍历dp数组。
  3. 判断回文链表
    
    解题思路：
    
    我们知道，判断一个字符串是否为回文串很简单，只要从两边向中间逼近即可，使用左右双指针技巧即可。但是，单链表无法倒着遍历，无法使用双指针技巧，那么怎么办呢？
    
    最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。
    
    其实，我们也可以使用后序遍历的技巧，不用新的链表也可以倒着遍历原始链表。
    
    最后，我们有更加简单的方法：使用快慢指针，找到单链表的中点，即fast指针比slow指针快一倍，当fast指针遍历完毕后，slow一定是链表的中间点（如果链表个数为奇数，即fast指针不为null，则需要让slow指针继续前进一格），最后，从slow指针开始反转后半部分链表，然后比较是否是回文链表。
  4. 让字符串成为回文串的最少插入次数
    
    解题思路：
    
    如下1312.【让字符串成为回文串的最少插入次数】

LeetCode算法

LeetCode算法
1. 1312.【让字符串成为回文串的最少插入次数】
  
  解题思路：
  
  首先，要找最少的插入次数，那肯定要穷举出所有的情况，找到最少的那个。暴力算法穷举出所有插入方法，时间复杂度是多少？每次都可以在两个字符的中间插入任意一个字符，外加判断字符串是否为回文字符串，因此算法必定是指数级别的。
  
  因此，考虑使用动态规划来做。
  
  回文问题一般都是从字符串的中间向两端扩散，构造回文串也是类似的。
  
  我们定义一个二维的dp数组，dp[i][j]的定义如下：对字符串s[i..j]，最少需要进行dp[i][j]次插入才能变成回文串，我们想求整个s的最少插入次数，根据这个定义，也就是想求dp[0][n-1]的大小
  
  base case 也很容易想到，当i == j时dp[i][j] = 0，因为当i == j时s[i..j]就是一个字符，本身就是回文串，所以不需要进行任何插入操作
  
  接下来，就是找状态转移方程了，利用数学归纳法思考状态转移方程。
  
  状态转移就是从小规模问题的答案推导更大规模问题的答案，就是从 base case 向其他状态推导。如果我们现在想计算dp[i][j]的值，假设我们已经计算出了子问题dp[i+1][j-1]的值了，想办法推出dp[i][j]的值。
  
  既然已经算出dp[i+1][j-1]，即知道了s[i+1..j-1]成为回文串的最小插入次数，那么也就可以认为s[i+1..j-1]已经是一个回文串了，所以通过dp[i+1][j-1]推导dp[i][j]的关键就在于s[i]和s[j]这两个字符。
  
  因此，对于s[i]和s[j]要分情况讨论：如果s[i]==s[j]，我们不需要进行任何插入，因此插入次数沿用上个状态的即可；s[i]!=s[j]，如果要构成回文串，则最简单的想法就是，先把s[j]插到s[i]右边，同时把s[i]插到s[j]右边，这样构造出来的字符串一定是回文串，但是，这种方法不一定是插入次数最少，我们应该这样想，比如第[i...j-1]个本身就是回文串，则只需要将第s[j]的插入到s[i]前面即可，不需要像前面一样插入两次，同理对于第[i+1...j]个本身就是回文串的情况也是，因此，如果对于[i...j-1]或[i+1...j]为回文串，则选择两个插入次数最小的+1即为s[i]!=s[j]的情况下的[i...j]变为回文串的插入次数。
  
  至此，状态转移方程就可以列出来了：
```
 if (s[i] == s[j]) {
     dp[i][j] = dp[i+1][j-1];
 } else {
     dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
 }
```
  最后，根据base case和状态转移方程，选择遍历方式。我们选择从下到上，从左到右遍历。
  
  完整代码如下：
```
 public int minInsertions(String s) {

 // dp数组
 int[][] dp = new int[s.length()][s.length()];
 // base case，Java默认int数组元素就为0

 char[] charArray = s.toCharArray();

 // 从下到上遍历
 for (int i = s.length() - 2; i >= 0; i--) {
     // 从左到右遍历
     for (int j = i + 1; j < s.length(); j++) {
         if (charArray[i] == charArray[j]) {
             dp[i][j] = dp[i + 1][j - 1];
         } else {
             dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
         }
     }
 }

 return dp[0][s.length() - 1];

}
```
2. 647.【回文子串】
  
  解题思路：
  
  用经典寻找回文串的思路来解题即可。

2021/06/15 今日算法

知识点

LeetCode算法