JS算法-分割回文串

简介: JS算法-分割回文串

题目


给你一个字符串 s,请你将 **s **分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

输入: s = "aab"
输出: [["a","a","b"],["aa","b"]]


题解


我们这里声明两个函数,分别是isPalindromepartition函数。 isPalindrome 的功能是判断一个字符串是否是回文的。该函数首先将传入的字符串 s 分割成单个字符的数组 token,然后利用双指针方法,分别指向第一个和最后一个字符,同时从两端遍历比较字符是否一致。如果两个字符不同,则说明该字符串不是回文的,返回 false,如果两个字符相同,则继续往中间靠拢。当左指针大于等于右指针时,说明该字符串是回文的,返回 true。函数 partition 的功能是将一个字符串 s 拆分成回文子串的所有可能组合。该函数首先定义了一个空数组 ans,后面用于存储所有可能的回文组合情况。然后定义了一个递归函数 subStr,用于在字符串中从前往后依次尝试组合每一个回文子串。函数 subStr 接收三个参数,分别是当前遍历到的字符在字符串中的下标 index、当前组合的字符串 str、已组合好的子串数组 arr。函数 subStr 的主体是一个循环体,该循环体的作用是对下一个字符进行判断和组合。首先尝试将下一个字符添加到当前组合字符串 str 后面,继续递归调用 subStr。然后判断当前组合字符串是否是回文的,如果不是回文的,则直接返回。如果是回文的,则将当前组合字符串 str 添加到已组合好的子串数组 arr 中,再递归调用 subStr 继续向后组合,同时将已组合好的子串数组 arr 作为参数传入下一个递归调用。当所有字符都遍历完成后,将已组合好的子串数组 arr 添加到结果集数组 ans 中。最后,函数 partition 在调用递归函数 subStr 时,传入当前遍历到的第一个字符和一个空的已组合好的子串数组 []。当递归函数 subStr 执行完成后,函数 partition 将结果集 ans 返回

 var isPalindrome = function(s) {
      let token = s.split("");
      if(token.length === 0) return true;
      let i = 0,j = token.length-1;
      while(j>i){
          if(token[i] === token[j]){
              i++;j--;
          }else{
              return false;
          }
      }
      return true;
  };
  var partition = function(s) {
      let len = s.length;
      let ans = [];
      function subStr(index,str,arr){
          if(index>=len){
              ans.push(arr.slice());
              return;
          }
          if(index+1<len) subStr(index+1,str+s[index+1],arr);
          if(!isPalindrome(str)) return;
          arr.push(str);
          subStr(index+1,s[index+1],arr);
          arr.pop();
      }
      subStr(0,s[0],[]);
      return ans;
  }
相关文章
|
21天前
|
JavaScript 算法 安全
深度剖析:共享文件怎么设置密码和权限的 Node.js 进阶算法
在数字化时代,共享文件的安全性至关重要。本文聚焦Node.js环境,介绍如何通过JavaScript对象字面量构建数据结构管理文件安全信息,包括使用`bcryptjs`库加密密码和权限校验算法,确保高效且安全的文件共享。通过实例代码展示加密与权限验证过程,帮助各行业实现严格的信息资产管理与协作。
|
1月前
|
存储 监控 算法
局域网网络管控里 Node.js 红黑树算法的绝妙运用
在数字化办公中,局域网网络管控至关重要。红黑树作为一种自平衡二叉搜索树,凭借其高效的数据管理和平衡机制,在局域网设备状态管理中大放异彩。通过Node.js实现红黑树算法,可快速插入、查找和更新设备信息(如IP地址、带宽等),确保网络管理员实时监控和优化网络资源,提升局域网的稳定性和安全性。未来,随着技术融合,红黑树将在网络管控中持续进化,助力构建高效、安全的局域网络生态。
48 9
|
2月前
|
监控 算法 JavaScript
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
49 7
|
1月前
|
存储 监控 JavaScript
深度探秘:运用 Node.js 哈希表算法剖析员工工作时间玩游戏现象
在现代企业运营中,确保员工工作时间高效专注至关重要。为应对员工工作时间玩游戏的问题,本文聚焦Node.js环境下的哈希表算法,展示其如何通过快速查找和高效记录员工游戏行为,帮助企业精准监测与分析,遏制此类现象。哈希表以IP地址等为键,存储游戏网址、时长等信息,结合冲突处理与动态更新机制,确保数据完整性和时效性,助力企业管理层优化工作效率。
33 3
|
5月前
|
算法 JavaScript 前端开发
第一个算法项目 | JS实现并查集迷宫算法Demo学习
本文是关于使用JavaScript实现并查集迷宫算法的中国象棋demo的学习记录,包括项目运行方法、知识点梳理、代码赏析以及相关CSS样式表文件的介绍。
第一个算法项目 | JS实现并查集迷宫算法Demo学习
|
6月前
|
JavaScript 算法 前端开发
JS算法必备之String常用操作方法
这篇文章详细介绍了JavaScript中字符串的基本操作,包括创建字符串、访问特定字符、字符串的拼接、位置查找、大小写转换、模式匹配、以及字符串的迭代和格式化等方法。
JS算法必备之String常用操作方法
|
4月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
50 0
|
3月前
|
JavaScript 前端开发
JavaScript中的原型 保姆级文章一文搞懂
本文详细解析了JavaScript中的原型概念,从构造函数、原型对象、`__proto__`属性、`constructor`属性到原型链,层层递进地解释了JavaScript如何通过原型实现继承机制。适合初学者深入理解JS面向对象编程的核心原理。
48 1
JavaScript中的原型 保姆级文章一文搞懂
|
7月前
|
JavaScript Java 测试技术
基于springboot+vue.js+uniapp的客户关系管理系统附带文章源码部署视频讲解等
基于springboot+vue.js+uniapp的客户关系管理系统附带文章源码部署视频讲解等
135 2
|
3月前
JS+CSS3文章内容背景黑白切换源码
JS+CSS3文章内容背景黑白切换源码是一款基于JS+CSS3制作的简单网页文章文字内容背景颜色黑白切换效果。
33 0

热门文章

最新文章