leetcode: 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.

原问题链接：https://leetcode.com/problems/longest-palindromic-substring/

 

问题分析

    这个问题的目标是求一个字符串里最长的回文子串。那么什么是回文串呢？我们来看一些示例。从最基本的开始，比如空串：""， 长度为1的字符串，像"a", "b", "c", " "等。对于更长一些的字符串呢？

比如长度为偶数的串，像"aa", "abba"，这种的情况恰好将整个串分成相等的两个部分，我们只需要从最中间的两个点开始往两头遍历比较就可以了。还有一种情况，对于长度为奇数的串，像"aba", "aabaa"等。这种的查找方式则是首先找到最中心的点，然后分别从这个点的前面一个位置和后面一个位置这两个点向两头遍历比较。

    这个时候，如果我们来构造这个程序，可以从字符串s的开头到结尾的每个元素，按照前面的两种方式去向前向后遍历查找符合条件的回文。假设当前位置的索引为i, 往前往后的两个元素分别为l, r。查找可以继续的条件无非是l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)。这样我们就构造了这么一个循环。在循环里每次和我们给定的全局变量maxLen比较。如果找到的长度大于maxLen，则将maxLen设置成我们当前的长度。而当前的长度值就是r - l + 1。

    按照前面的讨论，我们可以得到一个如下的程序：

 

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;
        int start = 0, end = 0, maxLen = 1;
        for(int i = 0; i < s.length(); i++) {
            int l = i - 1, r = i + 1; 
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                if(r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    start = l;
                    end = r;
                }
                l--;
                r++;
            }
            l = i; 
            r = i + 1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                if(r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    start = l;
                    end = r;
                }
                l--;
                r++;
            }
        }
        return s.substring(start, end + 1);
    }
}

     这里，我们声明了3个变量，start, end, maxLen。分别表示求得的当前最大回文的起始点，终结点以及长度。后面的两个循环里，每次通过设定l, r的两个起始位置，然后进行比较和设定。这样可以得到最终最长的回文子串。程序里还有一个值得注意的地方就是对于程序一些边界条件的判断。比如s == null || s.length() <= 1。对于这种情况我们可以直接返回s。

    如果从纯粹对付这个程序问题的角度来说，上述程序已经够了。但是从改善代码的角度来说，如果我们希望能够写得更加简洁，上述代码还是有很多可以改进的地方的。我们一一看过来。

    首先一个就是上面的两个循环基本上是干差不多的事情的，无非就是它们遍历的两个点的起始值不一样。我们完全可以把它们提出来作为一个方法。这样只要将不同的值作为参数传进去就可以了。当然，这样将这些重复的部分提出来作为一个方法之后，原来设定的几个变量像start, end, maxLen必须设置成类的成员变量。

    另外一个，我们比较的时候是取的r - l + 1和maxLen。而实际上我们真的有必要专门用maxLen这个变量吗？已经有了start, end之后maxLen本身就是等于end - start + 1的。所以实际上我们完全可以用r - l + 1和end - start + 1来比较。既然只是比较它们的差，两边的这个加一其实也就没有必要了。这样我们可以得到一个简洁很多的代码：

 

public class Solution {
    int start = 0, end = 0;
    public String longestPalindrome(String s) {
        if(s == null || s.length() <= 1) return s;
        for(int i = 0; i < s.length(); i++) {
            updateLongest(i - 1, i + 1, s);
            updateLongest(i, i + 1, s);
        }
        return s.substring(start, end + 1);
    }
    
    private void updateLongest(int l, int r, String s) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            if(r - l > end - start) {
                start = l;
                end = r;
            }
            l--;
            r++;
        }
    }
}

 

总结

    这个问题本身并不难。主要是针对几种情况的讨论，在字符串为空，长度小于等于1以及长度为奇数和偶数的情况下怎么去判断筛选。这里选择的循环的条件就比较讲究。另外，如果我们去想办法改进代码，会发现完全可以采用一种很简洁的方式解决这个问题。这种简约的美，你懂的:)