当前位置：首页 > article >正文

一起学习LeetCode热题100道（61/100）

article 2024/11/19 19:25:08

61.分割回文串(学习)

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

示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

提示：
1 <= s.length <= 16
s 仅由小写英文字母组成

解析：
一、变量定义
1.result：一个数组，用于存储所有可能的分割方案。
2.current：一个数组，用于在回溯过程中构建当前的分割方案。

二、辅助函数：isPalindrome
1.这个函数检查传入的字符串str是否是回文串。它通过比较字符串的首尾字符，并逐步向中心移动，来验证整个字符串是否对称。

三、回溯函数：backtrack
1.这是解决问题的核心函数。它使用回溯算法来尝试所有可能的分割方式。
2.基准情况：如果start等于字符串s的长度，说明已经遍历完整个字符串，此时将current（当前的分割方案）添加到result中。
3.循环遍历：从start开始，遍历字符串s的剩余部分。对于每个位置i，截取从start到i（包含i）的子串。
4.检查回文：使用isPalindrome函数检查截取的子串是否是回文串。
5.添加并继续：如果是回文串，则将其添加到current中，并递归调用backtrack(i + 1)来继续处理剩余的字符串。
6.撤销选择：回溯结束后，需要从current中移除最后添加的子串，以便尝试其他可能的分割方式。

四、调用回溯函数
1.在partition函数的末尾，通过调用backtrack(0)开始回溯过程，从字符串的起始位置开始尝试所有可能的分割。

var partition = function (s) {
    const result = [];
    const current = [];

    // 辅助函数：检查子串是否是回文串  
    function isPalindrome(str) {
        let left = 0;
        let right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 回溯函数  
    function backtrack(start) {
        // 如果已经遍历完整个字符串，则将当前分割方案添加到结果中  
        if (start === s.length) {
            result.push([...current]);
            return;
        }

        for (let i = start; i < s.length; i++) {
            // 截取从start到i的子串  
            const substring = s.substring(start, i + 1);
            // 检查子串是否是回文串  
            if (isPalindrome(substring)) {
                // 如果是回文串，则将其添加到当前分割方案中  
                current.push(substring);
                // 继续向后回溯  
                backtrack(i + 1);
                // 回溯结束，撤销选择  
                current.pop();
            }
        }
    }

    backtrack(0);
    return result;
};```