LeetCode题解131.palindrome-partitioning

题目地址

https://leetcode.com/problems/palindrome-partitioning/description/

题目描述

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
  ["aa","b"],
  ["a","a","b"]
]

思路

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

关键点解析

• 回溯法

代码

• 语言支持：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

相关题目

• 39.combination-sum
• 40.combination-sum-ii
• 46.permutations
• 47.permutations-ii
• 78.subsets
• 90.subsets-ii
• 113.path-sum-ii

LeetCode题解125.valid-palindrome

题目地址 https://leetcode.com/problems/valid-palindrome/description/ 题目描述 Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. …

LeetCode题解堆排序和快速排序

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法，其中 n 为数据规模。 那么两者谁更快呢？ 为什么？题解：快排最坏情况下是O(n^2)，平均和最好是O(nlogn) ，堆排序始终为O(nlogn)，还是堆排序快吧

LeetCode题解斜着遍历

遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索， 而搜索的核心就是遍历，而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能，而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候， 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历， 更少有情况是斜着遍历。那么这次就考考你， 怎么斜着遍历一个二…

LeetCode题解砝码的最小数量

假设有三种重量的砝码，2g、3g、7g，对于任意重量物品，请设计一个函数getResult(weight)，接收一个参数weight，返回所需砝码的最小数量。输入示例：const weight = 100;输出示例：getResult(weight) // 15 其中7g的14个，2g的1个题解：```phpfunction getResult($weigh…

LeetCode题解93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源：力扣（LeetCode）链接：https://le…