昨天的日期很具有紀念意義，“20200202”正好是一段回文，很多朋友也在朋友圈記錄了這有意義的一刻。
那么什么是回文呢？就是從前往后，和從后往前完全一致的字符串，就是一段回文了。
如果我們把回文隱藏在其他一段字符串中，例如“122320200202111”或者“202002029982”，能否用程序快速的找出它呢？
正好leetcode上就有這么一個問題，我們來看看：

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"

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

1. 例如“bb”這種回文，一個指針a指向當前字符，另一個指針b指向下一個字符；當a和b的值相等時a--，b++繼續(xù)循環(huán)判斷是否相等，直到不相等或者指針越界后中斷。
2. 例如“aba”這種回文，一個指針a-1指向當前字符的前一個字符，另一個指針b指向下一個字符；當a和b的值相等時a--，b++繼續(xù)循環(huán)判斷是否相等，直到不相等或者指針越界后中斷。

好了，這經(jīng)過分析，這兩種方法唯一的不同就是指針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ù)使用兩個數(shù)組指針j和scanIndex，代表分析過程中的a和b進行運算，s就是原始的字符串。同時我們通過公共變量進行最大值的保存和判斷。
我們再來加上調(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;
    }

在這里我們加上了邊界判斷條件，以及之前分析的兩個分支判讀，分別進行調(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"進行測試，得到預(yù)期的返回：

image.png

image.png

image.png