C/C++教程

[Leetcode 5] 最长回文子串Longest Palindromic Substring

本文主要是介绍[Leetcode 5] 最长回文子串Longest Palindromic Substring,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

问题

求最长回文子串,即左右对称

Given a string s, return the longest palindromic substring in s.

 

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

 

思路

俩种情况,ab ba和ab b ba

回文串,经典的DP,第[i][j]是否为回文,由[i+1][j-1]&&本身决定(除了*

*tips: 对角线恒为true,i-j<2时,是否为回文,只由s.i是否等于s.j决定(图中三角形)

 

 

 

 

代码

*注意循环顺序,因为上下三角本质是一样的,为了更快,只用选其中一个三角

*选了三角后要注意扫的方向,从前往后可能[i+1][j-1]还没被赋值

 

    public static String longestPalindrome(String s) {
        int n = s.length();
        String res = null;

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

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j <n; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && ((j-i)<2||dp[i + 1][j - 1]);

                if (dp[i][j] && (res==null|| j - i + 1 > res.length())) {
                    res = s.substring(i, j + 1);
                }
            }
        }

        return res;
    }

 

这篇关于[Leetcode 5] 最长回文子串Longest Palindromic Substring的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!