昨天的日期很具有紀(jì)念意義纱新，“20200202”正好是一段回文，很多朋友也在朋友圈記錄了這有意義的一刻穆趴。
那么什么是回文呢脸爱？就是從前往后，和從后往前完全一致的字符串未妹，就是一段回文了簿废。
如果我們把回文隱藏在其他一段字符串中，例如“122320200202111”或者“202002029982”络它，能否用程序快速的找出它呢族檬？
正好leetcode上就有這么一個(gè)問(wèn)題，我們來(lái)看看：

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.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"

此問(wèn)題是需要找到一個(gè)字符串中長(zhǎng)度最長(zhǎng)的一段回文化戳。
思路如下：我們遍歷整個(gè)字符串中的每個(gè)字符单料，假設(shè)指針a指向當(dāng)前的字符，需要有兩個(gè)分支判讀：

1. 例如“bb”這種回文迂烁，一個(gè)指針a指向當(dāng)前字符看尼，另一個(gè)指針b指向下一個(gè)字符；當(dāng)a和b的值相等時(shí)a--盟步，b++繼續(xù)循環(huán)判斷是否相等藏斩，直到不相等或者指針越界后中斷。
2. 例如“aba”這種回文却盘，一個(gè)指針a-1指向當(dāng)前字符的前一個(gè)字符狰域，另一個(gè)指針b指向下一個(gè)字符媳拴；當(dāng)a和b的值相等時(shí)a--，b++繼續(xù)循環(huán)判斷是否相等兆览，直到不相等或者指針越界后中斷屈溉。

好了，這經(jīng)過(guò)分析抬探，這兩種方法唯一的不同就是指針a的初始化值不同子巾，那么我們可以提取公共的函數(shù)：

    int max = 0;
    String result = "";

    void scanMatched(String s, int j, int scanIndex) {
        while(j >=0 && scanIndex < s.length()) {
            if (s.charAt(j) == s.charAt(scanIndex)) {
                j--;
                scanIndex++;
            } else {
                break;
            }
        }
        int matched = scanIndex - (j + 1);
        if (max < matched) {
            max = matched;
            result = s.substring(j + 1, scanIndex);
        }
    }

此函數(shù)使用兩個(gè)數(shù)組指針j和scanIndex，代表分析過(guò)程中的a和b進(jìn)行運(yùn)算小压，s就是原始的字符串线梗。同時(shí)我們通過(guò)公共變量進(jìn)行最大值的保存和判斷。
我們?cè)賮?lái)加上調(diào)用方法：

    public String longestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 2) {
            return s;
        }
        if (s.length() == 2) {
            return s.charAt(0) == s.charAt(1) ? s : s.substring(0, 1);
        }
        
        for (int i = 0; i < s.length() - 1; i++) {
            int j = i - 1;
            int scanIndex = i + 1;
            scanMatched(s, j, scanIndex);
            scanMatched(s, i, scanIndex);
        }
        return result;
    }

在這里我們加上了邊界判斷條件怠益，以及之前分析的兩個(gè)分支判讀仪搔，分別進(jìn)行調(diào)用，組裝后完整的代碼如下：

class Solution {
    int max = 0;
    String result = "";
    
    public String longestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 2) {
            return s;
        }
        if (s.length() == 2) {
            return s.charAt(0) == s.charAt(1) ? s : s.substring(0, 1);
        }
        
        for (int i = 0; i < s.length() - 1; i++) {
            int j = i - 1;
            int scanIndex = i + 1;
            scanMatched(s, j, scanIndex);
            scanMatched(s, i, scanIndex);
        }
        return result;
    }
    
    void scanMatched(String s, int j, int scanIndex) {
        while(j >=0 && scanIndex < s.length()) {
            if (s.charAt(j) == s.charAt(scanIndex)) {
                j--;
                scanIndex++;
            } else {
                break;
            }
        }
        int matched = scanIndex - (j + 1);
        if (max < matched) {
            max = matched;
            result = s.substring(j + 1, scanIndex);
        }
    }
}

首先我們帶入"122320200202111"進(jìn)行測(cè)試蜻牢，得到預(yù)期的返回：

image.png

image.png

image.png