# 题目
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, and there exists one unique longest palindromic substring.
# 思路
暴力破解（我和我同学也喜欢叫爆破）：
先固定下标，再固定长度，这样就能取出字符串。判断字符串是否是回文串且长度比原来的回文串长，若是，更新，若否，继续取字符串。
// brute force: time O(n ^ 3) space O(n) result: TLE
public string LongestPalindrome(string s)
{
char[] strs = s.ToCharArray();
, end = ;
; i < strs.Length; i++) // start by index i
{
; j > i; j--) // end by index j
{
if (strs[i] == strs[j])
{
bool isPalindrome = true;
, l = j - ; k < l; k++, l--) // check whether substring is palindrome or not
{
if (strs[k] != strs[l])
{
isPalindrome = false;
break;
}
}
if (isPalindrome && j - i > end - start) // compare
{
start = i;
end = j;
}
}
}
}
);
}
暴力破解，时间复杂度O(n ^ 3)，空间复杂度O(n)，时间TLE。
我思维有点固化了。总想着先取字符串来判断是否是回文串，其实可以假定它是回文串，看它到底有多长。下面两个方法就是这样思考的。
优化暴力破解：
对于每一个字符，分奇偶，分别尝试去找最长的回文串，并记录长度。
// reference: https://discuss.leetcode.com/topic/23498/very-simple-clean-java-solution
// optimize brute force: time O(n ^ 2) space O(n) result: 156ms
public void palindrome(char[] strs, int left, int right, ref int start, ref int length) // judge palindrome
{
&& right <= strs.Length - && strs[left] != strs[right]) return;
>= && right + <= strs.Length - && strs[left - ] == strs[right + ])
{
left--;
right++;
}
;
if (length < newLength)
{
start = left;
length = newLength;
}
}
// optimize brute force : time O(n ^ 2) space O(n) result:
public string LongestPalindrome(string s)
{
) return s;
, length = ;
char[] strs = s.ToCharArray();
; i < strs.Length; i++)
{
palindrome(strs, i, i, ref start, ref length); // recrusively judge
palindrome(strs, i, i + , ref start, ref length);
}
return s.Substring(start, length);
}
优化暴力破解，时间复杂度O(n ^ 2)，空间复杂度O(n)，时间153ms。
优化遍历：
对于每一个字符，尝试去找最长的回文串，采取以下方法：
1、若是重复串，跳过重复部分（重复串怎么样都是回文串）。
2、非重复串，正常比对头尾。
3、设置下一个字符为非重复部分的下一个字符。
比如baaaaab，遇到第一个a的时候，直接忽略5个a（也就是默认他是回文串了），从b开始尝试寻找回文串。同时下一个需要判断的字符是从第二个b开始。
# 解决（优化遍历）
// reference: https://discuss.leetcode.com/topic/12187/simple-c-solution-8ms-13-lines/
// like cheating method: time O(n ^ 2) space O(n) result: 132ms
public string LongestPalindrome(string s)
{
char[] strs = s.ToCharArray();
, maxLength = , start = ;
)
{
int k = i, j = i; // j is left, i is middle, k is right
&& strs[k] == strs[k + ]) k++; // skip duplicate char
i = k + ; // set next begin index, we can skip duplicate char
&& k < s.Length - && strs[j - ] == strs[k + ]) // check palindrome
{
j--;
k++;
}
;
if (newLength > maxLength) // compare
{
start = j;
maxLength = newLength;
}
}
return s.Substring(start, maxLength);
}
优化遍历，时间复杂度O(n ^ 2)，空间复杂度O(n)，时间132ms。
# 题外话
动态规划也可以做。
具体参考https://discuss.leetcode.com/topic/23498/very-simple-clean-java-solution/12。
状态转移方程：palindrome[i][j] = palindrome[i + 1][j - 1] && s[i] == s[j] 。palindrome[i][j]表示s[i]到s[j]是否是回文串。
题主太懒了，交给你们了。
# 测试用例
static void Main(string[] args)
{
_5LongestPalindromicSubstring solution = new _5LongestPalindromicSubstring();
Debug.Assert(solution.LongestPalindrome("dddddd") == "dddddd", "wrong 1");
Debug.Assert(solution.LongestPalindrome("abbacdef") == "abba", "wrong 2");
Debug.Assert(solution.LongestPalindrome("cabbadef") == "abba", "wrong 3");
Debug.Assert(solution.LongestPalindrome("cabba") == "abba", "wrong 4");
Debug.Assert(solution.LongestPalindrome("caacbbbbbad") == "bbbbb", "wrong 5");
string veryLong = "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee";
Debug.Assert(solution.LongestPalindrome(veryLong) == veryLong, "wrong 6");
Debug.Assert(solution.LongestPalindrome("a") == "a", "wrong 7");
Debug.Assert(solution.LongestPalindrome("abb") == "bb", "wrong 8");
}
# 地址
Q： https://leetcode.com/problems/longest-palindromic-substring/
A： https://github.com/mofadeyunduo/LeetCode/blob/master/5LongestPalindromicSubstring/5LongestPalindromicSubstring.cs
（希望各位多多支持本人刚刚建立的GitHub和博客，谢谢，有问题可以邮件609092186@qq.com或者留言，我尽快回复）