当前位置：首页 > JavaScript

力扣131 js实现

2026-01-31 00:56:40JavaScript

力扣131（分割回文串）的JavaScript实现

力扣131题要求将给定字符串分割成若干子串，使得每个子串都是回文串。以下是JavaScript的实现方法：

回溯算法实现

回溯法是解决这类问题的常见方法，通过递归尝试所有可能的分割方式。

function partition(s) {
    const result = [];
    backtrack(s, 0, [], result);
    return result;
}

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

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

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

动态规划优化回文判断

可以预先用动态规划计算所有子串是否为回文，减少重复计算。

力扣131 js实现

function partition(s) {
    const n = s.length;
    const dp = Array(n).fill().map(() => Array(n).fill(false));
    const result = [];

    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= i; j++) {
            if (s[i] === s[j] && (i - j <= 2 || dp[j+1][i-1])) {
                dp[j][i] = true;
            }
        }
    }

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

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

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