美文网首页算法代码
最长回文子串

最长回文子串

作者: windUtterance | 来源:发表于2020-05-23 20:12 被阅读0次

    题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。回文是一个正读和反读都相同的字符串。

    示例:输入: "babad" 输出: "bab"

    Java代码

    class Solution {
        //动态规划
        public String longestPalindrome(String s) {
            int n = s.length();
            if(n < 2) return s;
            if(n == 0 || s == null) return "";
            int max = 1, begin = 0;
    
            //matrix[i][j]表示s[i][j]是否是回文子串
            boolean[][] matrix = new boolean[n][n];
            char[] s_new = s.toCharArray(); //转换为数组可以避免使用s.charAt(i)操作增加算法运行时间
    
            for(int i = 0;i < n;i++) matrix[i][i] = true; //对角线元素也就是子串长度为1时,一定是回文子串
            for(int j = 1;j < n;j++) {
                for(int i = 0;i < j;i++) {
                    //matrix[i][j] = s_new[i] == s_new[j] && (j - i < 3 || matrix[i + 1][j - 1])
                    //下面的逻辑可以简化为上面这一句话,但是没有铺垫不好理解
                    if(s_new[i] != s_new[j]) matrix[i][j] = false;
                    else {
                        if(j - i < 3) matrix[i][j] = true;
                        else matrix[i][j] = matrix[i + 1][j - 1];
                    }
    
                    //当matrix[i][j]为true时,就表示s[i...j]是回文子串,此时记录子串长度和起始位置
                    if(matrix[i][j] && j - i + 1 > max) {
                        max = j - i + 1;
                        begin = i;
                    }
                }
            }
    
            return s.substring(begin, begin + max);
        }
    
    
        //暴力解法,时间复杂度为n的三次方
        public String longestPalindrome2(String s) {
            if(s == null || s.length() == 0) return "";
            int n = s.length();
            String max = "";
            for(int i = 0;i < n;i++) {
                for(int j = i;j < n;j++) {
                    if(isPalindrome(s.substring(i, j + 1)) && j - i + 1 > max.length())
                        max = s.substring(i, j + 1);
                }
            }
    
            return max;
        }
    
        public boolean isPalindrome(String s) {
            String d = new StringBuilder(s).reverse().toString();
            return s.equals(d);
        }
    }
    

    相关文章

      网友评论

        本文标题:最长回文子串

        本文链接:https://www.haomeiwen.com/subject/gfylahtx.html