songEagle

STAY CURIOUS. STAY HUMBLE.

【每日一题】(44题)编程题:分割回文字符串

每日一题 2021年02月19日 星期五 上午

【每日一题】(44题)编程题:分割回文字符串

作者:松宝写代码

过年期间,应感觉好久多天没有更新了,啪啪大脸

本来打算过年期间还是坚持更新的,只完成了对外版本的年终总结,但是还是被其他事情打断了。

昨天已经开工了,还是没有更新,抱歉。

算法题目

题目描述:

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

示例

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

解题思路

当起点和字符串一样长的时候,说明已经无剩余字符串可以裁剪了,停止,保存路径

var partition = function (str) {
  let ans = [];
  const backTrack = function (start, path) {
    //当起点和字符串一样长的时候,说明已经无剩余字符串可以裁剪了,停止,保存路径
    if (start == str.length) {
      ans.push(path);
      return;
    }
    for (let i = start; i < str.length; i++) {
      let strs = str.slice(start, i + 1);
      if (strs && isPalindrome(strs)) {
        //起始改为i+1,保存路径节点path.concat(strs)
        backTrack(i + 1, path.concat(strs));
      }
    }
  };
  backTrack(0, []);
  return ans;
};
//判断是否回文,该方法效率较低,仅为了书写方便
function isPalindrome(str) {
  return str.split("").reverse().join("") === str;
}

往期「每日一题」

1、JavaScript && ES6

2、浏览器

3、Vue

4、React

5、HTML5

6、算法

7、Node

8、Http

9、年终总结

谢谢支持

1、文章喜欢的话可以「分享,点赞,在看」三连哦。

2、作者昵称:saucxs,songEagle,松宝写代码。「松宝写代码」公众号作者,每日一题,实验室等。一个爱好折腾,致力于全栈,正在努力成长的字节跳动工程师,星辰大海,未来可期。内推字节跳动各个部门各个岗位

3、长按下面图片,关注「松宝写代码」,是获取开发知识体系构建,精选文章,项目实战,实验室,每日一道面试题,进阶学习,思考职业发展,涉及到JavaScript,Node,Vue,React,浏览器,http,算法,端相关,小程序等领域,希望可以帮助到你,我们一起成长~

松宝写代码

还没有评论,快来抢沙发吧!