No.005 Longest Palindromic Substring

5. Longest Palindromic Substring

  • Total Accepted: 120226
  • Total Submissions: 509522
  • Difficulty: Medium

  Given a string s, find the longest palindromic(回文) substring in sS. You may assume that the maximum length of s is 1000, and there exists one unique longest palindromic substring.

推荐解法3,直观,有效,好理解

方法一:暴力搜索(O(N³))

  这个思路就很简单了,就是直接求出每一个子串,然后判断其是否为回文。我们从子串长度最长开始,依次递减,如果遇到是回文的,则直接返回即可。循环结束如果没有回文,则返回null。

  值得注意的一点是因为题目直接说了肯定存在回文,并且最大长度的回文唯一,所以在当字符串长度大于1的时候,最大回文长度必定大于1(如果为1的话,则每一个单独字符都可以作为最长长度的回文),所以搜索长度递减到2就结束了。题目中肯定存在大于2的回文,所以不会直到最后循环结束返回null这一步,所以最后直接写的返回null无关紧要。

 1 /*
 2  * 方法一:暴力搜索
 3  */
 4 public String longestPalindrome(String s) {
 5     if (s == null || s.length() == 0 || s.length() == 1) {
 6         return s;
 7     }
 8 
 9     String sub;
10     for (int subLen = s.length(); subLen > 1; subLen--) {
11         for (int startIndex = 0; startIndex <= (s.length() - subLen); startIndex++) {
12             // 列出所有子串,然后判断子串是否满足有重复
13             if (startIndex != (s.length() - subLen)) {
14                 sub = s.substring(startIndex, startIndex + subLen);
15             } else {
16                 sub = s.substring(startIndex);
17             }
18             System.out.println(sub);
19             if (isPalindrome(sub)) {
20                 return sub;
21             }
22         }
23     }
24     
25     return null ;
27 }
28 
29 private boolean isPalindrome(String sub) {
30     for(int i = 0 ; i <= sub.length()/2 ; i++){
31         if(sub.charAt(i) != sub.charAt(sub.length()-i-1)){
32             return false ;
33         }
34     }
35     return true ;
36 }

方法二:动态规划O(N²)

更简洁的做法,使用动态规划,这样可以把时间复杂度降到O(N²),空间复杂度也为O(N²)。做法如下:

首先,写出动态转移方程。

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj ) ,显然,如果一个子串是回文串,并且如果从它的左右两侧分别向外扩展的一位也相等,那么这个子串就可以从左右两侧分别向外扩展一位。

其中的base case是

P[ i, i ] ← true P[ i, i+1 ] ← ( Si = Si+1 )

然后,看一个例子。

假设有个字符串是adade,现在要找到其中的最长回文子串。使用上面的动态转移方程,有如下的过程:

  按照红箭头->黄箭头->蓝箭头->绿箭头->橙箭头的顺序依次填入矩阵,通过这个矩阵记录从i到j是否是一个回文串。

 1 /*
 2  * 方法二:动态规划的方法
 3  */
 4 public String longestPalindrome2(String s) {
 5     if (s == null || s.length() == 0 || s.length() == 1) {
 6         return s;
 7     }
 8     char [] arr = s.toCharArray() ;
 9     int len = s.length() ;
10     int startIndex = 0 ; 
11     int endIndex = 0 ;
12     boolean [][] dp = new boolean [len][len] ;
13     dp[0][0] = true ;
14     for(int i = 1 ; i < len ; i++){
15         //dp[i][i]置为true
16         dp[i][i] = true ;
17         //dp[i-1][i]判断true或false
18         if(arr[i-1] != arr[i]){
19             dp[i-1][i] = false ;
20         }else{
21             dp[i-1][i] = true ;
22             startIndex = i-1 ;
23             endIndex = i ;
24         }
25     }
26     //填充其他地方的值
27     for(int l = 2 ; l < len ; l++){
28         for(int i = 0 ; i < len-l ; i++){
29             int j = i+l ; 
30             if(dp[i+1][j-1] && (arr[i] == arr[j])){
31                 dp[i][j] = true ;
32                 if((j-i) > (endIndex - startIndex)){
33                     startIndex = i ; 
34                     endIndex = j ;
35                 }
36             }
37         }
38     }
39     //返回最长回文字符串
40     if(endIndex == (len-1)){
41         return s.substring(startIndex) ;
42     }else{
43         return s.substring(startIndex, endIndex+1) ;
44     }            
45 }

  下面的方法参考自 http://blog.csdn.net/feliciafay/article/details/16984031

方法三:从中间向两边展开O(N²)(比动态规划方法好理解)

  回文字符串显然有个特征是沿着中心那个字符轴对称。比如aha沿着中间的h轴对称,a沿着中间的a轴对称。那么aa呢?沿着中间的空字符''轴对称。所以对于长度为奇数的回文字符串,它沿着中心字符轴对称,对于长度为偶数的回文字符串,它沿着中心的空字符轴对称。对于长度为N的候选字符串,我们需要在每一个可能的中心点进行检测以判断是否构成回文字符串,这样的中心点一共有2N-1个(2N-1=N-1 + N)。检测的具体办法是,从中心开始向两端展开,观察两端的字符是否相同。代码如下:

 1 //从中间向两边展开
 2 string expandAroundCenter(string s, int c1, int c2) {
 3   int l = c1, r = c2;
 4   int n = s.length();
 5   while (l >= 0 && r <= n-1 && s[l] == s[r]) {
 6     l--;
 7     r++;
 8   }
 9   return s.substr(l+1, r-l-1);
10 }
11  
12 string longestPalindromeSimple(string s) {
13   int n = s.length();
14   if (n == 0) return "";
15   string longest = s.substr(0, 1);  // a single char itself is a palindrome
16   for (int i = 0; i < n-1; i++) {
17     string p1 = expandAroundCenter(s, i, i); //长度为奇数的候选回文字符串
18     if (p1.length() > longest.length())
19       longest = p1;
20  
21     string p2 = expandAroundCenter(s, i, i+1);//长度为偶数的候选回文字符串
22     if (p2.length() > longest.length())
23       longest = p2;
24   }
25   return longest;
26 }

四、 时间复杂度为O(N)的算法

  在这里看到了更更简洁的做法,可以把时间复杂度降到O(N).具体做法原文说得很清楚,有图有例,可以仔细读读。这里我只想写写,为什么这个算法的时间复杂度是O(N)而不是O(N²)。从代码中看,for循环中还有个while,在2层嵌套的循环中,似乎应该是O(N²)的时间复杂度。

 1 // Transform S into T.
 2 // For example, S = "abba", T = "^#a#b#b#a#$".
 3 // ^ and $ signs are sentinels appended to each end to avoid bounds checking
 4 string preProcess(string s) {
 5   int n = s.length();
 6   if (n == 0) return "^$";
 7   string ret = "^";
 8   for (int i = 0; i < n; i++)
 9     ret += "#" + s.substr(i, 1);
10  
11   ret += "#$";
12   return ret;
13 }
14  
15 string longestPalindrome(string s) {
16   string T = preProcess(s);
17   int n = T.length();
18   int *P = new int[n];
19   int C = 0, R = 0;
20   for (int i = 1; i < n-1; i++) {
21     int i_mirror = 2*C-i; // equals to i' = C - (i-C)
22     
23     P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
24     
25     // Attempt to expand palindrome centered at i
26     while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
27       P[i]++;
28  
29     // If palindrome centered at i expand past R,
30     // adjust center based on expanded palindrome.
31     if (i + P[i] > R) {
32       C = i;
33       R = i + P[i];
34     }
35   }
36  
37   // Find the maximum element in P.
38   int maxLen = 0;
39   int centerIndex = 0;
40   for (int i = 1; i < n-1; i++) {
41     if (P[i] > maxLen) {
42       maxLen = P[i];
43       centerIndex = i;
44     }
45   }
46   delete[] P;
47   
48   return s.substr((centerIndex - 1 - maxLen)/2, maxLen);
49 }

  时间复杂度为什么是O(N)而不是O(N²)呢?

   假设真的是O(N²),那么在每次外层的for循环进行的时候(一共n步),对于for的每一步,内层的while循环要进行O(N)次。而这是不可能。因为p[i]和R是有相互影响的。while要么就只走一步,就到了退出条件了。要么就走很多很步。如果while走了很多步,多到一定程度,会更新R的值,使得R的值增大。而一旦R变大了,下一次进行for循环的时候,while条件直接就退出了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-79-单词搜索(用dfs解决)

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

3691
来自专栏我是业余自学C/C++的

线性表——链式描述(双向链表)

1433
来自专栏专知

Numpy教程第2部分 - 数据分析的重要功能

【导读】Numpy是python数据分析和科学计算的核心软件包。 上次介绍了numpy的一些基础操作。例如如何创建一个array,如何提取array元素,重塑(...

4619
来自专栏计算机视觉与深度学习基础

Leetcode 164 Maximum Gap 桶排序好题

Given an unsorted array, find the maximum difference between the successive ele...

2195
来自专栏wannshan(javaer,RPC)

dubbo负载均衡代码分析3(加权轮询策略)

接上篇 https://cloud.tencent.com/developer/article/1109577 加权轮询,我第一次没理解,个人觉得不好理解。于是...

4076
来自专栏数据结构与算法

洛谷P3327 [SDOI2015]约数个数和(莫比乌斯反演)

题目描述 设d(x)为x的约数个数,给定N、M,求 \sum^N_{i=1}\sum^M_{j=1}d(ij)∑i=1N​∑j=1M​d(ij) 输入输出格式 ...

2744
来自专栏GIS讲堂

Geotools中实现NC转等值面

前面的文章有实现IDW插值并生成等值面的,本文在前文基础上实现气象NC数据生成等值面。

3334
来自专栏小樱的经验随笔

华中农业大学第五届程序设计大赛网络同步赛题解

A.Little Red Riding Hood ? B.Choosy in Food •F[i]:从第I个点到终点的期望步数 •F[i] = (F[i +...

3577
来自专栏owent

POJ PKU 2549 Sumsets 解题报告

题目链接http://acm.pku.edu.cn/JudgeOnline/problem?id=2549

921
来自专栏数据结构与算法

P1888 三角函数

题目描述 输入一组勾股数a,b,c(a≠b≠c),用分数格式输出其较小锐角的正弦值。(要求约分。) 输入输出格式 输入格式: 一行,包含三个数,即勾股数...

3077

扫码关注云+社区

领取腾讯云代金券