一个字符串问题

Question

bobo老师，遇到这么一个求字符串子回文个数的问题，不知有什么好的解法没

这里字回文具体描述是，一串字符去掉当中的某一个或多个字符，剩下的不改变相对位置是回文即可（比如aba有5个子回文：a,b,a,aa,aba)

PS: 老师，字符串问题的算法之后会讲嘛: )

Answer 1

liuyubobobo 2017-09-02 04:10:08

还是蛮经典的动态规划问题。详细解释起来还有点复杂，在网上搜搜看？应该有不少讲解。

关于动态规划，在我的《玩儿转算法面试》的课程里有入门级别的介绍。但是动态规划算法的应用实在太灵活，如果真要枚举其中的“套路”的话，可能也要详细分析几十个相关的问题。我曾经思考过专门做一个动态规划的算法课程，不过现在暂时优先级没有排的特别高。学习动态规划需要多见问题，在刚开始肯定不是每个问题自己都能解决的，不过没关系，看别人的解决思路，总结经验。看多了，慢慢就有感觉了，什么样的问题能用动态规划解决。

至于字符串专属的经典问题，诸如kmp算法，bm算法，trie结构以及相应的优化等等等等，也计划在这个算法与数据结构的进阶课程中介绍。不过，暂时，优先级也没有那么高。主要是对于课程的选题，慕课网有市场的考量，暂时觉得进阶课程的市场空间可能会比较小：（

• liuyubobobo #1

  我在网上稍微搜了一下，比如这个：http://www.cnblogs.com/AndyJee/p/4465696.html 其实现在互联网资讯这么多，对于爱学习的人真的是一大福音啊！

• 提问者 gin_gin #2

  哇，谢谢老师！听了您的课感觉收获真是太大了，一个月前从C++语法都有些问题，现在已经能自己实现一些比较高效的算法了。等我消化几天就去听您的下一堂课。^_ *