最长回文子串问题

突然发现已经好久没有写博客了，虽然说最近一直都在补京阿尼的番还有一些猛男番确实是原因之一啦。不过最近确实是在看安卓这方面的东西，之前尝试着写了一点，但是我这个安卓也是小白，啥都不懂，只是在学一点儿基础，这好像也没啥好写的东西吖。于是就上leetcode看看，没想到前面的第五题我竟然都没写，不过通过率是低的真实，不用说，这肯定是一道比较难的题目了，下面就来看看这个题目吧。

题目的基本介绍

给定一个字符串s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”
输出: “bb”

这个题目看起来似乎是很简单的，不过说实话难的很。反正我是不会做的。而且这个题目的解法是真的特别的多，有很多的神仙解法，把这些的只适用于这道题目的神仙解法都研究透了，似乎这也没有什么意义，所以这里我要介绍的也就是这道题目的最简单的也是最复杂的解法——使用动态规划来解决。

思路分析

动态规划算法之前就已经说过了，不过当时似乎没有写什么例子，也没做做过多的说明。不过，动态规划的基本思路我们还是明白的。找到子问题不同状态之间的关联，也就是那个递推的公式。比如说背包问题，放三样东西和放两样东西之间的关联是如何的。找到了这样的公式，问题也就可以轻松的解决了。

这道题目其实也蛮类似的。我们假定i和j分别指向字符串的头和尾，我们要知道i-j这一块是回文串，那么我们就可以得到i+1-j-1这一块肯定也是字符串，而且i处的字符要等于j处的字符。这时我们就可以得到一个关系表达式：

这个递推的表达式，说实话是蛮简单的了，不过不理解动态规划的算法确实很难想出来，反正我是没有想出来的。不过看懂还是可以看懂的(到头来，做了那么多的动态规划的题目，遇到这种题目根本不知道用动态规划，也不明白如何用动态规划，可悲可悲,明天可以把之前做的那四个动态规划的题目给总结了)

这样动态规划的思路就用了，如何使用代码来实现呢？

上面的f(i, j)很容易的想到使用二维数组来实现，和背包问题是类似的。f(i, j)表示的意思就是i-j是否是回文串（i和j都是包含的）

代码实现

#include <iostream>
#include <vector>
using namespace std;


class Solution {
public:
    static string longestPalindrome(string s) {
        int length = s.length();
        if(length == 0 || length == 1){
            return s;
        }
        int max_len=1;
        int max_start=0;

        bool** f= new bool*[length];

        for (int i=0; i<length; i++){
            f[i] = new bool[length];
        }

        // 这个似乎不初始化也是对的
        // for (int i=0; i<length; i++){
        //     for (int j=0; j<length; j++){
        //         f[i][j] = false;
        //     }
        // }
        for(int j=0;j<length;j++){
            int i=0;
            f[j][j]=true;
            for(;i<j;i++){
                f[i][j]=(s[j]==s[i]&&(j-i==1||f[i+1][j-1]));
                if(f[i][j] && j-i+1 > max_len){                   
                    max_len = j-i+1;
                    max_start = i;
                }        
            }                       
        }
        return s.substr(max_start, max_len);
    }
};

int main(int argc, char const *argv[])
{
    cout<<Solution::longestPalindrome("abbbbdsfdsga")<<endl;

    system("pause");
    return 0;
}

代码说明：

  1. 堆上的二维数组

    因为这里我使用的C++，不是Java。所以说在堆上new一个二维数组这种玩意的事，我是真的没用过。问了网上，他们都推荐使用vector,不过这个vector还是要resize的要给定vector一个大小才能够那样像数组一样的使用

    vector<vector<bool>> f;
for (int i=0; i<length; i++){
    f.emplace_back(vector<bool>(length, false));
}

    这样确实是一个好办法，不过new二维数组也不是难事，我一开始是这样子干的。

    bool** f = new bool[length][length];

    不过，很遗憾，报错了，不可以在堆上new出一个二维的数组，这里是C++，这里不是Java。

    那怎么办呢？我又尝试了这样子的

    bool** f = new bool[length];
for (int i=0; i<length; i++){
    f[i] = new bool[length];
}

    这个方法也确实是够蠢的，new返回的是bool*，我却使用bool**来接收，这是肯定错误的啊。

    后来查了资料才知道，原来可以这样子干啊。

    bool** f = new bool*[length];
for (int i=0; i<length; i++){
    f[i] = new bool[length];
}

    这样子就搞定了，第一个new返回的是bool**类型的，第二个new返回的是bool*类型的，

    这样子堆上的一个二维数组的问题也就解决了。那为啥不用vector呢？可以用，而且作为使用C++的程序员，最好就别使用这种C类型的数组的。但是为了满足好奇心，这次就使用一下子。(C++11中stl中出现了array，其实说真的我们已经不需要C类型的任何数组和，无论是堆上的还是常量区上的，C++中都有对应的数据结构，stl就是这么强大)

    1. for循环内

      和背包问题是类似的，我们可以先只是取前面几个字符串，然后每次加一个字符。j就是代表着取的字符串的最后的位置（包含）。每次都将f[j][j]置为true，因为此时字符串长度为1这肯定是回文的。然后然i从0开始到j判断f[i][j]的值，也就是说此时j永远是结束的那个位置。而j又是从0开始的到length-1结束，也就是所有的情况都会被遍历的。而这个算法的时间复杂度从这儿就很容易的得出来是O(n2)，空间复杂度也是O(n2)，算得上是一个比较低效的算法了，就这个题目有O(n), O(n)的算法，不过我也不需要去了解了，看过多的骚算法也不好，反正也用不到，费脑细胞。

    2. f[i][j]=(s[j]==s[i]&&(j-i==1||f[i+1][j-1]));

      这个就是使用的上面的那个递推的表达式，不过有点儿不同。我在后面加入了j-i==1，这时也就是说字符串的长度就是2，这是是不能进行后面的那个递推的，所以要单独拎出来。

      至于后面的那个判断也就是看看找到的回文字符串的长度有没有最大的大，如果有的话就把他记下来，而且还要把开始的位置记下来，因为函数返回的字符串不是长度。刚好c++中的substr()这个函数就两个参数，第一个参数是开始的索引，第二个位置是字符串的长度。

      return s.substr(max_start, max_len);

      如果是Java的话就不是这样子了。Java当中的substring()函数（为啥不是subString？这明显不符合Java函数的驼峰式的命名规范啊。。。）的第一个参数是开始的索引，第二个参数的结束的索引（不包含）

      return s.substring(max_start, max_start+max_len);

总结

动态规划算法算是很常见的了，如果理解了这个算法，会发现这个算法其实代码很好写，就是找那个递推的关系。不过我现在也就是停留在能做成做过的动态规划的题目，如果真的是给我一道算法的题目，我真的不知道是否该用动态规划算法，如果要用又是怎么用呢？唉，还是太菜了，对这个算法的理解还不够。

赏

一枚小菜鸡