Dx's Tech Notes

3.最长回文子串

2 min read

  • 2.19
    • 7.分割回文串相同，但这里直接用 boolean 数组进行判断不需要辅助函数
    • 且从后开始遍历，j 从 i 开始往后移动
class Solution {
    public String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        String res = "";
        for(int i=s.length()-1;i>=0;i--){
            for(int j=i;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j)&&(j-i<3||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
                if(dp[i][j]==true&&j-i+1>res.length()){
                    res = s.substring(i,j+1);
                }
            }
        }
        return res;
    }
}

、

  • dp为i-j是否为回文串,用(用substring(i,j+1))更新string
if (s[i] == s[j]) {
    if (j - i < 3) dp[i][j] = true;  // "aa" 或 "aba" 这种短串自动回文
    else dp[i][j] = dp[i+1][j-1];
}
class Solution {
    public String longestPalindrome(String s) {
        boolean[][]dp = new boolean[s.length()][s.length()];
 
        String res = "";
 
        for(int i=s.length()-1;i>=0;i--){
            for(int j=i;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j)&&(j-i<3||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
                if(dp[i][j]&&j-i+1>res.length()){
                    res = s.substring(i,j+1);
                }
            }
        }
        return res;
    }
}
class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String res = "";
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j) && (j-i<3||dp[i+1][j-1])){
                    dp[i][j]=true;
                }
                if(dp[i][j]&&j-i+1>res.length()){
                    res = s.substring(i,j+1);
                }
            }
        }
        return res;
    }
}
  • i从尾部往开头走,j从i开头往前走,
  • 判断条件:如果ij相等在判断是否小于3或者里面的i+1,j-1是否相等,成功就标记true
  • 如果刚刚成功,且相减大于目前的回文串,则更新(用substring(i,j+1))更新string

Graph View