回文题相关题目

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

关键点：字符串，不是子序列，统计个数

class Solution {
    public int countSubstrings(String s) {
        int len=s.length();
        int sum=0;
        for(int i=0;i
            int left=i/2;
            int right=left+i%2;
            while(left>=0 && right
                left--;
                right++;
                sum++;
            }
        }
        return sum;
    }
}

给你一个字符串 s，找到 s 中最长的回文子串。

关键点：字符串，不是子序列，统计最长长度

class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        String res="";
        for (int i = 0; i < len*2-1; i++) {
            int left=i/2;
            int right=left+i%2;
            while(left>=0 && right
                String temp=s.substring(left,right+1);
                if(temp.length()>res.length()){
                    res=temp;
                }
                left--;
                right++;
            }
        }
        return res;
    }
}

上述两题都需要遍历每个回文中心点，从0到len*2-1，从中心点向左右扩展判断

上述两题都是字符串，而516.最长回文子序列考察的是子序列，不是子串，解决这道子序列题需要用1143. 最长公共子序列的方法

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1=text1.length(),len2=text2.length();
        int[][] dp=new int[len1+1][len2+1];
        for(int i=1;i<=len1;++i){
            for(int j=1;j<=len2;++j){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}

这道题使用动态规划解决。

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int len=s.length();
        int[][] dp=new int[len+1][len+1];
        for(int i=1;i<=len;++i){
            for(int j=1;j<=len;++j){
                if(s.charAt(i-1)==s.charAt(len-j)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[len][len];
    }
}

如果把一个字符串反转，那么字符串中的回文子序列包含的字符在反转前后位置不会发生变化，然后我们寻找反转前后两个字符串的最长公共子序列，得到的结果就是最长回文子序列