5. Longest Palindromic Substring 【Medium】

avatar 2020年08月30日13:10:21 6 1941 views
博主分享免费Java教学视频,B站账号:Java刘哥

Question

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

 

 

My Answer 1

暴力求解,超时,时间复杂度 O(n^3)

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String maxStr = "";
        for(int i = 0; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                String temp = s.substring(i,j);
                if(isPalindromic(temp) && temp.length() > maxStr.length()) {
                    maxStr = temp;
                }
            }
        }
        return maxStr;
    }
    
    // 字符串是否回归
    private boolean isPalindromic(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}

 

My Answer2

动态规划 O(n^2)

 

class Solution {
    
    // 动态规划, 避免做重复运算,已经算过的直接拿来用
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";

        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // 情况1:如果i和j字符相同,且子串长度小于等于3,则一定是回归串;如 a,aa,aba
                // 情况2:如果i和j字符相同,且 (i+1,j-1) 的子串也是回文串,则一定是回文串 如 abcba, 当前 i=0,j=5
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                
                if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
    
}

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

avatar 登录者:匿名
匿名评论,评论回复后会有邮件通知

  

已通过评论:0   待审核评论数:0