每日一道算法题——最长回文字串

2019-11-10 17:22:08

字体：大中小

来源：转载

供稿：网友

最长回文字串

题目 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”

分析寻找一个字符串的最长回文字串，题目很容易理解。很容易想到的解决办法：把每个字母当做回文串的中心字母，向两半延伸判断是否是回文串，并记录下最长的字符串。时间复杂度为O(n^2) 这个比暴力求解要好，暴力求解是把所有字串找出来，然后判断是否是回文串，时间复杂度为O(n^3)。

代码

public String longestPalindrome(String s) { if(s.length()<=1) return s; int start = 0,len = 0 ; //从下标为1的字符开始，把当前字符当做中心字符向两边延伸判断 for(int i = 1;i<s.length();i++){ //回文串长度为偶数 int low = i-1,high = i ; while(low>=0 && high <s.length() && s.charAt(low) == s.charAt(high) ){ low --; high ++; } if(high - low- 1 > len){ len = high - low - 1; start = low +1; } //回文串长度为奇数 low = i-1;high = i+1 ; while(low>=0 && high <s.length() && s.charAt(low) == s.charAt(high) ){ low --; high ++; } if( high - low - 1 > len){ len =high - low- 1; start = low +1; } } return s.substring(start,start+len); }