No.005：Longest Palindromic Substring，no.005palindromic
題目：
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.
官方難度:
Medium
翻譯：
給定一個字符串S，找出最長回文子串，你可以假定字符串的最長長度為1000，並且只有一個最長回文子串。
例子：
"cabcbaabcaa"的最長回文子串是"cbaabc"
思路：
1.最長回文子串是對稱的，那麼在遍歷字符串的時候，被遍歷的字符串要被當成對稱中心而不是子串開始位置來考慮。
2.形如"cbaabc"和"cbabc"都是回文子串，所以需要兩次考慮。
解題中可能遇到的困難：
1.如果使用String.split("")的方法，形成的數組第一個元素是空字符串，無論從效率還是使用方面，String.toCharArray()是更優的選擇。
2.理論上來說，分析一個字符串的雙核對稱的情況，需要分左右兩種情況考慮，但是實際上這一次的有對稱就是下一個字符串的做對稱，沒必要多做一次分析。
3.由於是從中心往外擴，隨時注意可能出現的數組越界問題。
4.在遍歷到中心偏後的位置，根據以下可能達到的最長字串的長度和當前最長子串的長度比較，可以少做幾次循環。
解題代碼：
![]()
1 // 返回一個長度為2的數組，第一位是startIndex，第二位是length
2 private static int[] method(String str) {
3 // str.split("")方法生成的字符串，長度+1，第一個是空字符串
4 char[] array = str.toCharArray();
5 int maxLength = 0;
6 int startIndex = 0;
7 // 循環中使用，先聲明
8 int count1;
9 int count2;
10 for (int i = 0; i < array.length; i++) {
11 // 超過字符串一半之後，理論上可能達到的最大長度小於當前的最大長度，直接退出循環
12 if (i > (array.length - 1) / 2 && 2 * (array.length - 1 - i) + 1 < maxLength) {
13 break;
14 }
15 count1 = singleCore(i, array);
16 count2 = doubleCore(i, array);
17 // 存在超過最大長度的情況
18 if (count1 > maxLength || count2 > maxLength) {
19 // 不存在相等情況
20 if (count1 > count2) {
21 // 單核
22 maxLength = count1;
23 startIndex = i - (count1 - 1) / 2;
24 } else {
25 // 雙核
26 maxLength = count2;
27 startIndex = i + 1 - (count2 / 2);
28 }
29 }
30 }
31 // 返回結果
32 int[] result = new int[2];
33 result[0] = startIndex;
34 result[1] = maxLength;
35 return result;
36 }
37
38 // 單核處理
39 private static int singleCore(int index, char[] array) {
40 // 長度計數器
41 int count = 1;
42 // 擴展次數，單核長度為1自對稱，不判斷
43 int extendTime = 1;
44 // 直到外擴超過數組范圍，一直循環
45 while (index - extendTime >= 0 && index + extendTime < array.length) {
46 // 不對稱，直接跳出
47 if (array[index - extendTime] != array[index + extendTime]) {
48 break;
49 }
50 extendTime++;
51 count += 2;
52 }
53 return count;
54 }
55
56 // 雙核處理，沒有必要考慮左和右的問題，因為這一次的右就是下一次的左
57 private static int doubleCore(int index, char[] array) {
58 // 返回長度
59 int count = 0;
60 // 右雙核的情況，最後一位排除
61 if (index != array.length - 1) {
62 int extendTime = 0;
63 // 雙核的出界點的基礎是不同的
64 while (index - extendTime >= 0 && index + extendTime + 1 < array.length) {
65 if (array[index - extendTime] != array[index + 1 + extendTime]) {
66 break;
67 }
68 extendTime++;
69 count += 2;
70 }
71 }
72 return count;
73 }
View Code
測試代碼地址：
https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q005.java
LeetCode題目地址：
https://leetcode.com/problems/longest-palindromic-substring/
PS：如有不正確或提高效率的方法，歡迎留言，謝謝！
