[LeetCode5]Longest Palindromic Substring

本文主要是介绍[LeetCode5]Longest Palindromic Substring，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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, and there exists one unique longest palindromic substring.

定义函数
P[i,j] = 字符串区间[i,j]是否为palindrome.

首先找个例子，比如S="abccb",
S= a b c c b
Index = 0 1 2 3 4

P[0,0] =1 //each char is a palindrome
P[0,1] =S[0] == S[1] , P[1,1] =1
P[0,2] = S[0] == S[2] && P[1,1], P[1,2] = S[1] == S[2] , P[2,2] = 1
P[0,3] = S[0] == S[3] && P[1,2], P[1,3] = S[1] == S[3] && P[2,2] , P[2,3] =S[2] ==S[3], P[3,3]=1
......................
由此就可以推导出规律

P[i,j] = 1 if i ==j
= S[i] ==S[j] if j = i+1
= S[i] == S[j] && P[i+1][j-1] if j>i+1

实现如下：

public String longestPalindrome(String s) {int len = s.length();boolean [][] pal = new boolean[len][len];for(int i=0;i<len;i++){for(int j=0;j<len;j++)pal[i][j] = false;}int start = 0;int end = 0;int mLen = 0;for(int i=0;i<len;i++){for(int j=0;j<i;j++){pal[j][i] = (s.charAt(i)==s.charAt(j) && ((i-j<2) || pal[j+1][i-1]));if(pal[j][i] && mLen<i-j+1){mLen = i-j+1;start = j;end = i;}}pal[i][i] = true;}return s.substring(start, end+1);}

遍历整个字符串，以每个字符串为中心搜索回文并记录

c++

string longestPalindrome(string s) {int startIndex = 0;int len = 0;int sI, eI;for(int i=0; i< s.size()-1; i++){if(s[i] == s[i+1]){sI = i;eI = i+1;Search(s, sI, eI, len, startIndex);}sI = i;eI = i;Search(s, sI, eI, len, startIndex);}if(len ==0)len = s.size();return s.substr(startIndex,len);}void Search(string &s, int sI, int eI, int &len, int &startIndex){int step = 1;while((sI-step)>=0 && (eI+step)<s.size()){if(s[sI-step] != s[eI+step]){ break;}step++;}int wid = eI-sI+2*step-1;if(wid>len){len = wid;startIndex = sI-step +1;}
}

这篇关于[LeetCode5]Longest Palindromic Substring的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---