LeetCode刷题：5. Longest Palindromic Substring-白红宇

LeetCode刷题：5. Longest Palindromic Substring

阅读量：4040 次

发布时间：2019-05-24

本文共 1494 字，大约阅读时间需要 4 分钟。

LeetCode刷题：5. Longest Palindromic Substring

原题链接：

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

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Example:

Input: “cbbd”

Output: “bb”

题目的意思是给定一个字符串s，找到字符串s中的最长回文子串。

假设字符串s的最大长度为1000。

算法设计

采用动态规划算法求解。

　　假设

dp[i][j] d p [ i ] [ j ] $dp[ i ][ j ]$ 的值为true，表示字符串s中下标从 i 到 j 的字符组成的子串是回文串。那么可以推出：

dp[ i ][ j ] = dp[ i + 1][ j - 1] && s[ i ] == s[ j ] dp[ i ][ j ] = dp[ i + 1][ j - 1] && s[ i ] == s[ j ] $dp[ i ][ j ] = dp[ i + 1][ j - 1] && s[ i ] == s[ j ]$ 。

　　这是一般的情况，由于需要依靠

i+1,j−1 i + 1 , j − 1 $i+1, j -1$ ，所以有可能

i+1=j−1,i+1=(j−1)−1 i + 1 = j − 1 , i + 1 = ( j − 1 ) − 1 $i + 1 = j -1, i +1 = (j - 1) -1$ ，因此需要求出基准情况才能套用以上的公式：

i+1=j−1 i + 1 = j − 1 $i + 1 = j -1$ ，即回文长度为1时，

dp[i][i]=true d p [ i ] [ i ] = t r u e $dp[ i ][ i ] = true$ ;

i+1=(j−1)−1 i + 1 = ( j − 1 ) − 1 $i +1 = (j - 1) -1$ ，即回文长度为2时，

dp[i][i+1]=（s[i]==s[i+1]） d p [ i ] [ i + 1 ] = （ s [ i ] == s [ i + 1 ] ） $dp[ i ][ i + 1] = （s[ i ] == s[ i + 1]）$ 。

算法设计

public static String longestPalindrome(String s) {        // n表示字符串的长度        int n = s.length();        String res = null;        // 定义一个dp数组        boolean[][] dp = new boolean[n][n];        // 外层循环控制从最后一个字符向第一个字符渐进        for (int i = n - 1; i >= 0; i--) {            // 内层循环控制            for (int j = i; j < n; j++) {                // dp数组元素                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;    }

(完）

转载地址：http://yztdi.baihongyu.com/

你可能感兴趣的文章