“20200202”正好是一段“回文”,如何快速在一个字符串里找

昨天的日期很具有纪念意义，“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"

此问题是需要找到一个字符串中长度最长的一段回文。
思路如下：我们遍历整个字符串中的每个字符，假设指针a指向当前的字符，需要有两个分支判读：

1. 例如“bb”这种回文，一个指针a指向当前字符，另一个指针b指向下一个字符；当a和b的值相等时a--，b++继续循环判断是否相等，直到不相等或者指针越界后中断。
2. 例如“aba”这种回文，一个指针a-1指向当前字符的前一个字符，另一个指针b指向下一个字符；当a和b的值相等时a--，b++继续循环判断是否相等，直到不相等或者指针越界后中断。

好了，这经过分析，这两种方法唯一的不同就是指针a的初始化值不同，那么我们可以提取公共的函数：

    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);
        }
    }

此函数使用两个数组指针j和scanIndex，代表分析过程中的a和b进行运算，s就是原始的字符串。同时我们通过公共变量进行最大值的保存和判断。
我们再来加上调用方法：

    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;
    }

在这里我们加上了边界判断条件，以及之前分析的两个分支判读，分别进行调用，组装后完整的代码如下：

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"进行测试，得到预期的返回：

image.png
我们再带入另一个分支的测试用例"ccbbbbda"，依然成功：
image.png
最后提交代码，成绩马马虎虎吧^_
image.png
这个空间复杂度是O(1)，但是时间复杂度基本上是O(n^2)了，那么有没有更好的方式呢？嗯。。。留给读者来给我答案吧。