最大回文串

感觉像我这样智商的人，是找不到工作了。。前些天一公司笔试题求最大回文串问题，搞得我一脸懵，百度一下各种算法满天飞，各种晕。。。

回文串

回文串指的是顺着读和逆着读是一样的字符串，如abcba，这就是一个标准的回文串。

各种解决方法

其实当我第一时间看到这题的时候，我也不是很懵，想到了正则。。 具体题目要求好像是返回最长回文串的长度，贴出当时的傻傻代码。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function huiwen (str) {
            var reg 
            var max = parseInt(str.length/2)
            var makereg = function (max) {
                reg = '(\\w?)'
                for(var i=0; i<max ;i++){
                    reg = '(\\w)'+reg
                }
                for(;max>0;max--){
                    reg =reg+'(\\'+max+')'
                }
                return new RegExp(reg,'g')
            }
            var getMax = function(arr) {
                var Max = 0
                arr.forEach(function(item){
                        if(item.length>Max) Max = item.length
                    })
                return Max
            }
            for (var test,output ; max>=0; max--) {
                test = makereg(max)
                if(output = str.match(test)) {
                    return getMax(output)
                }
            }
        }

当然，当初第一次写的时候并没有这么完美，至少忘记了考虑str长度为1的情况,也没有考虑到最后匹配的output可能长度有两个的情况，反正就是惨。。。这个其实意义不怎么大，为了用正则而正则，其实就是用来装逼的。。然后装逼还不怎么成功，复杂度还高（好的，其实我不太懂复杂度，数据结构都见鬼去吧。。）

然后听了某大神的话，看了下动态规划（一种算法，我等渣渣一脸懵逼。。）

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
我无耻地复制了别人的一段话。。原文链接然而我并不能太看懂
最后贴上一个求最大回文串解决方案大全。。http://blog.csdn.net/fendouzhe123/article/details/39496299
里面详细说明了几种方法。。虽然我看得很懵逼。