学习记录：js算法（八十八）：分割回文串

文章目录

- 分割回文串
- - 思路一：回溯法
  - 思路二：动态规划
  - 方法三：记忆化搜索
  - 方法四：迭代法
  - 方法五：位运算

分割回文串

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

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

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

思路一：回溯法

function isPalindrome(str) {
    let left = 0, right = str.length - 1;
    while (left < right) {
        if (str[left] !== str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

function partition(s, start = 0, path = [], result = null) {
    if (result === null) {
        result = [];
    }
    
    if (start === s.length) {
        result.push([...path]);
        return result;
    }
    
    for (let i = start; i < s.length; i++) {
        if (isPalindrome(s.slice(start, i + 1))) {
            path.push(s.slice(start, i + 1));
            partition(s, i + 1, path, result);
            path.pop(); // 回溯
        }
    }
    return result;
}

function partitionPalindromes(s) {
    return partition(s);
}

讲解
使用回溯结合简单的回文检测来解决

定义辅助函数 isPalindrome:
○ 这个函数用于判断一个字符串是否为回文串。
○ 使用两个指针分别从字符串的头部和尾部向中心移动并比较字符是否相等。
定义递归函数 partition:
○ 参数包括：
■ s: 原始输入字符串。
■ start: 当前处理的子串起始位置。
■ path: 用于存储当前递归路径上的回文子串。
■ result: 最终结果数组，用于收集所有满足条件的分割方案。
○ 终止条件：当 start 等于字符串长度时，将 path 加入到结果数组 result 中。
○ 递归逻辑：
■ 遍历从 start 到字符串末尾的所有位置 i。
■ 如果从 start 到 i 的子串是回文串，则将其加入到 path 中。
■ 对剩余的字符串（从 i+1 开始）继续执行相同的操作。
■ 在递归结束后，从 path 中移除刚刚添加的子串，进行回溯。
调用 partition 函数:
○ 在主函数 partitionPalindromes 中，直接调用 partition 函数，无需额外参数，因为默认值已经设置好。

思路二：动态规划

var partition = function (s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(false));
    const result = [];

    // 预处理回文
    for (let end = 0; end < n; end++) {
        for (let start = end; start >= 0; start--) {
            if (s[start] === s[end] && (end - start <= 2 || dp[start + 1][end - 1])) {
                dp[start][end] = true;
            }
        }
    }

    function backtrack(start, path) {
        if (start === n) {
            result.push([...path]);
            return;
        }

        for (let end = start; end < n; end++) {
            if (dp[start][end]) {
                path.push(s.slice(start, end + 1));
                backtrack(end + 1, path);
                path.pop();
            }
        }
    }

    backtrack(0, []);
    return result;
};

思路：

使用动态规划预处理字符串中的所有回文子串，以便在生成分割方案时快速查找。
创建一个二维数组 dp，其中 dp[i][j] 表示从索引 i 到 j 的子串是否为回文。
先填充 dp 数组，然后使用回溯算法生成分割方案。

步骤：

初始化一个二维数组 dp，并根据回文的定义填充它。
使用嵌套循环遍历字符串，标记所有的回文子串。
定义 backtrack 函数，使用 dp 数组来检查子串是否为回文。
当找到一个回文子串时，加入路径并继续递归，直到到达字符串末尾。

方法三：记忆化搜索

function isPalindrome(str) {
    return str === str.split('').reverse().join('');
}

function partition(s) {
    const result = [];
    const memo = {};

    function backtrack(start, path) {
        if (start === s.length) {
            result.push([...path]);
            return;
        }

        for (let end = start + 1; end <= s.length; end++) {
            const substring = s.slice(start, end);
            if (memo[substring] === undefined) {
                memo[substring] = isPalindrome(substring);
            }
            if (memo[substring]) {
                path.push(substring);
                backtrack(end, path);
                path.pop();
            }
        }
    }

    backtrack(0, []);
    return result;
}

思路：

结合回溯法和记忆化搜索，避免重复计算回文检查。
使用一个缓存对象 memo 来存储已经检查过的子串的回文结果。

步骤：

定义 isPalindrome 函数来检查回文。
在 partition 函数中，定义 backtrack 函数，尝试每个可能的子串。
在检查子串是否为回文时，首先查看 memo 是否已有结果，如果没有，则进行检查并存储结果。
继续回溯，直到找到所有可能的分割方案。

方法四：迭代法

function partition(s) {
    const result = [];
    const stack = [[0, []]];

    while (stack.length) {
        const [start, path] = stack.pop();

        if (start === s.length) {
            result.push(path);
            continue;
        }

        for (let end = start + 1; end <= s.length; end++) {
            const substring = s.slice(start, end);
            if (substring === substring.split('').reverse().join('')) {
                stack.push([end, [...path, substring]]);
            }
        }
    }

    return result;
}

思路：

使用迭代而非递归来生成所有可能的分割方案。
使用栈来存储当前的起始位置和分割路径。

步骤：

初始化一个栈，并将起始位置和空路径压入栈中。
当栈不为空时，弹出栈顶元素。
如果当前起始位置等于字符串长度，则将当前路径添加到结果中。
遍历从当前起始位置到字符串末尾的所有可能子串，检查它们是否为回文。
如果是回文，则将其加入路径并将新的状态压入栈中。

方法五：位运算

function isPalindrome(str) {
    return str === str.split('').reverse().join('');
}

function partition(s) {
    const n = s.length;
    const result = [];
    const totalCombinations = 1 << n; // 2^n

    for (let i = 0; i < totalCombinations; i++) {
        const path = [];
        let lastIndex = 0;

        for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
                const substring = s.slice(lastIndex, j + 1);
                if (isPalindrome(substring)) {
                    path.push(substring);
                    lastIndex = j + 1;
                }
            }
        }

        if (lastIndex === n) {
            result.push(path);
        }
    }

    return result;
}