专栏首页编程JS实现计算最少回文切割数

JS实现计算最少回文切割数

作者注:算法能力一直是程序猿最基础也是最重要的一项基础能力,记得Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书,书名叫作《算法 + 数据结构 = 程序》,算法与数据结构之于程序设计的重要性不言自明,作者本身也非常注重基础算法能力的培养,除了平常阅读一些算法书籍如《算法导论》、《算法》《数据结构与算法Java语言描述》外,也非常关注一些公众号提供的有关算法的描述跟讲解,但是这些算法的描述一般都是只会给出一些伪代码或者思路。我的公众号里我会不定期的对一些常见算法做讲解,并用js语言实现出来,共读者参考~

----------- 正文分割线 ---------

题目重现:

对一个字符串按照回文进行分割,例如ababbbabbababa就是字符串ababbbabbababa的一个回文分割,每一个字串都是一个回文。请找到可以分割的最少的字串数。例如:

ababbbabbababa最少4个字符串,分割三次:ababbbabbababa

如果字符串整体是回文,则需要0次分割,最少1个字符串

实现思路:

我们的基本思路是这样:首先,找出所有的回文子串(见下面分析),然后找出所有可以对整个字符串进行回文分割的实现方案,最后我们从这些所有可行方案中找出切割术最少的方案(可能不只一种)即为我们想要的结果。我们一步步来详细分析。

回文子串的查找

该如何更好的判断回文呢?我们设定P[i][j]:

为true时,表示str[i..j]为回文

为false时,表示str[i..j]不是回文

则,当:

i==j时,P[i][j]=true

j==i+1时,P[i][j]=str[i]==str[i]

其他,P[i][j]=P[i+1][j-1]&&(str[i]==str[j])

这个P该如何构建呢?根据其状态转移的方程,P[i][j]所代表的字符串,长度从1开始变化,逐渐到整个字符串,是这样的一个构建的过程,所以外层循环应该是所要判断的字串的长度。基本代码如下:

js代码实现如下:

我们以符号"_"来分割开始和结束位置,比如从字符串的第二个字符到第5个字符是个子回文,那么上述函数返回的结果中属性'2_5'为TRUE,否则为false.

获取所有的回文分割可行方案

这里的实现方案比较多,比如对所有的回文子串创建树结构,对树进行广度优先遍历,找到最浅的遍历方案的等。我结合了js语言的特性,运用hash来进行处理。当然也可以考虑用数组实现。思路如下:

我们可以获取所有的单个字符开头的回文子串的数组,并组装成一个hash,然后对hash进行遍历,在另一个对象中(或以数组实现也可),找到以当前遍历属性(以"_"分隔)的开始值减一为结尾的所有属性组成数组,再将当前属性链接上去,最终该对象的所有属性值都是实现回文分割的解决方案。最后,我们只需要再次遍历数组,找到所有切割数最少的方案即可。

所有代码

所有的代码实现如下。其中可能还有可以优化的地方,可再仔细琢磨一下。

本文来自企鹅号 - 从前端er到全栈er媒体

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python基础2字符串

    String 字符串是Python中最常用的数据类型,可以用单引号和双引号创建字 符串,字符串是不可变的。 字符串的基本操作:Python内建序列包括(列表、元...

    企鹅号小编
  • 机器学习之Python基础(一)

    标题 Python语言特点 基本数据类型 循环 文件IO 函数 1 1 1 Python是一种面向对象的解释型计算机程序设计语言。它有着代码简洁、可读性强的特点...

    企鹅号小编
  • 任鸟飞谈逆向-《梦三国》字符串突破口以及跳回游戏领空

    在逆向很多数据的时候 无论是PC端还是移动端,我们都会借用到字符串去当突破口 今天只是说说PC端的字符串突破口,移动端下个月忙完手里的工作,分享给大家,我们系统...

    企鹅号小编
  • 算法君带你学算法(1):求最长回文字符串

    算法小白:最近一直在研究算法,刷了很多算法题,正好活动活动大脑,来来来,赶快出题!

    蒙娜丽宁
  • 计算机网络之网络层- 路由算法与路由协议

    如果两个结点间有边, 例如从结点X到结点Y,则从结点X到结点Y耗费的费用记做C(X,Y)=10。

    越陌度阡
  • 20190624一周文章阅读和收藏: 图像分类、检测,NLP,Python编程

    打算每周整理下这周看过觉得不错的文章,主要是机器学习、深度学习、Python编程方向的,包括但不局限于论文、综述、有趣的项目以及工具教程推荐,目前这个系列的名字...

    kbsc13
  • SQLServer 学习笔记之超详细基础SQL语句 Part 9

    -----------------------接Part 8-------------------

    授客
  • Bash中尖括号的更多使用方法

    在上一篇文章当中,我们介绍了尖括号(<>)以及它们的一些用法。在这篇文章,我们继续来深入探讨尖括号的更多其它用法。

    砸漏
  • 盘点丨开发者必备:基于 Linux 生态的十大 AI 开源框架

    前不久,AI 科技评论曾盘点了一系列机器学习相关的开源平台,包括谷歌的TensorFlow、微软的CNTK以及百度的PaddlePaddle等等。这些平台各具特...

    AI科技评论
  • C语言编程入门之--第一章初识程序

      导读:计算机程序无时不刻的影响着人类的生活,现代社会已经离不开程序,程序的作用如此巨大,那么程序到底是什么呢?本章主要讨论程序的概念,唤起读者对程序的兴趣,...

    啊源股

扫码关注云+社区

领取腾讯云代金券