Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

131. Palindrome Partitioning

My accepted JavaScript solution to LeetCode problem 131, Palindrome Partitioning, running in 13ms.

  • Difficulty: Medium
  • JavaScript
  • Runtime 13ms
  • Memory 79.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

JavaScript

Accepted on LeetCode — runtime 13ms, memory 79.5MB, accepted 2025-12-24.

javascript
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const result = [];
    const n = s.length;
    
    // Precompute palindrome table
    const dp = Array(n).fill(null).map(() => Array(n).fill(false));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i; j < n; j++) {
            if (s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    
    const backtrack = (start, path) => {
        if (start === n) {
            result.push([...path]);
            return;
        }
        
        for (let end = start; end < n; end++) {
            if (dp[start][end]) {
                path.push(s.substring(start, end + 1));
                backtrack(end + 1, path);
                path.pop();
            }
        }
    };
    
    backtrack(0, []);
    return result;
};

Source