1. 首页

LeetCode 131. 分割回文串

题目描述

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

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

难度:Middle

前置知识

  • 回溯法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一道求解所有可能性的题目, 这时候可以考虑使用回溯法。 回溯法解题的模板我们已经在很多题目中用过了,
这里就不多说了。大家可以结合其他几道题目加深一下理解。

这种题目其实有一个通用的解法,就是回溯法。网上也有大神给出了这种回溯法解题的通用写法,这里的所有的解法使用通用方法解答。
除了这道题目还有很多其他题目可以用这种通用解法,具体的题目见后方相关题目部分。

这里我画了一个图:

LeetCode 131. 分割回文串

图是 78.subsets,都差不多,仅做参考。

关键点解析

  • 回溯法

代码

  • 语言支持:JS,Python3
/*
 * @lc app=leetcode id=131 lang=javascript
 *
 * [131] Palindrome Partitioning
 */

function isPalindrom(s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right && s[left] === s[right]) {
    left++;
    right--;
  }

  return left >= right;
}
function backtrack(s, list, tempList, start) {
  const sliced = s.slice(start);

  if (isPalindrom(sliced) && tempList.join("").length === s.length)
    list.push([...tempList]);

  for (let i = 0; i < sliced.length; i++) {
    const sub = sliced.slice(0, i + 1);
    if (isPalindrom(sub)) {
      tempList.push(sub);
    } else {
      continue;
    }
    backtrack(s, list, tempList, start + i + 1);
    tempList.pop();
  }
}
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
  // "aab"
  // ["aa", "b"]
  // ["a", "a", "b"]
  const list = [];
  backtrack(s, list, [], 0);
  return list;
};
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        """回溯法"""

        res = []

        def helper(s, tmp):
            """
            如果是空字符串,说明已经处理完毕
            否则逐个字符往前测试,判断是否是回文
            如果是,则处理剩余字符串,并将已经得到的列表作为参数
            """
            if not s:
                res.append(tmp)
            for i in range(1, len(s) + 1):
                if s[:i] == s[:i][::-1]:
                    helper(s[i:], tmp + [s[:i]])

        helper(s, [])
        return res

相关题目

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 131. 分割回文串

链接:https://www.javascriptc.com/4495.html

« LeetCode 132. 分割回文串 II
骚年:Nginx 了解下»
Flutter 中文教程资源

相关推荐

QR code