5. 最长回文子串

标签:problems   链接   ges   bool   状态   har   最长回文子串   注意   res   

原题链接:https://leetcode-cn.com/problems/longest-palindromic-substring/

class Solution {
    // 思路:【动态规划】
    // 状态转移方程是 p[i,j] = p[i+1,j-1] && p[i] = p[j]
    //  p[i,j] 表示第i个 和 第j 个是相同的
    //  整体分两层循环【第一层按回文长度从零到n , 第二层就是字符从第一个开始往后循环】
    public String longestPalindrome(String s) {
        int n = s.length();
        // dp[i,j]=true 表示第i个 和 第j 个是相同的
        boolean[][] dp = new boolean[n][n];
        String res = "";
        // 回文长度的维度
        for (int length = 0; length < n; length++){
            for (int i = 0; i + length < n; i++){
                // i表示左边的下表,j 表示右边的下标
                int j = i + length;
                // 只有一个字符的时候
                if (length == 0){
                    dp[i][j] = true;
                } else if (length == 1){
                    // 只有两个字符的时候
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] =  (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && length + 1 > res.length()){
                    res = s.substring(i, i + length + 1);
                }
            }
        }
        return res;
    }
}



  注意点:

  1. 动态规划思维,能列出状态转移方程式并且能找到边界
  2. s.substring(a,b)函数的用法,取得范围注意是[a,b) ,左闭右开的区间,substring方法的s为小写,白板上写的时候要注意这个点。

5. 最长回文子串

标签:problems   链接   ges   bool   状态   har   最长回文子串   注意   res   

原文地址:https://www.cnblogs.com/junbaba/p/14164792.html

版权声明:完美者 发表于 2020-12-25 12:13:31。
转载请注明:5. 最长回文子串 | 完美导航

暂无评论

暂无评论...