1312. Minimum Insertion Steps to Make a String Palindrome

• Minimum Insertion Steps to Make a String Palindrome
• 给一个字符串，计算插入最少多少个字符可以让这个字符串成为回文字符串

思路

• 是一个动态规划题
• 这个题其实是算 LPS(Longest Palindromic Subsequence)，只需要计算最长的回文子序列长度，就可以知道还差几个字母。
• 用这个字符串的长度剪去最长子序列的长度，就是需要插入的字符串数量。
• 此外，在计算 LPS 的时候，因为递归函数经常会有重复计算，需要用一个 memo
• lps(i, j, s, memo)代表从 i 到 j 这段长度上 s 的最长子序列长度。

代码

class Solution {
    private int lps(int i, int j, String s, int[][] memo){
        int longest = 0;
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        if(i == j){
            return 1;
        }
        if(i > j){
            return 0;
        }
        if(s.charAt(i) == s.charAt(j)){
            longest = lps(i + 1, j - 1, s, memo) + 2;
        }else{
            longest = Math.max(
                lps(i + 1, j, s, memo),
                lps(i, j - 1, s, memo)
            );
        }
        memo[i][j] = longest;
        return longest;
    }

    public int minInsertions(String s) {
        int longest = lps(0, s.length() - 1, s, new int[s.length()][s.length()]);
        return s.length() - longest;
    }
}