Skip to content

Latest commit

 

History

History
120 lines (90 loc) · 2.54 KB

131.palindrome-partitioning.md

File metadata and controls

120 lines (90 loc) · 2.54 KB
Raw

题目地址

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

相关题目