131. Palindrome Partitioning

At a Glance

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: High
LeetCode: 131

Problem (one-liner)

Partition string s into substrings such that every piece is a palindrome; return all such partitions.

Recognition Cues

All valid splits — backtracking
Palindrome check each candidate prefix — precompute DP table for speed

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute — check palindrome by substring scan each time — O(n * 2^n) worse constant.
Optimal — DFS + isPalindrome memo or DP table pal[left][right] — same asymptotic, faster checks.

Optimal Solution

Go

func partition(s string) [][]string {
	result := [][]string{}
	path := make([]string, 0, len(s))

	var isPalindrome func(left int, right int) bool
	isPalindrome = func(left int, right int) bool {
		for left < right {
			if s[left] != s[right] {
				return false
			}
			left++
			right--
		}
		return true
	}

	var dfs func(start int)
	dfs = func(start int) {
		if start == len(s) {
			copied := make([]string, len(path))
			copy(copied, path)
			result = append(result, copied)
			return
		}
		for end := start + 1; end <= len(s); end++ {
			if isPalindrome(start, end-1) {
				path = append(path, s[start:end])
				dfs(end)
				path = path[:len(path)-1]
			}
		}
	}
	dfs(0)
	return result
}

JavaScript

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

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

  function dfs(startIndex) {
    if (startIndex === s.length) {
      result.push([...path]);
      return;
    }
    for (let endIndex = startIndex + 1; endIndex <= s.length; endIndex += 1) {
      if (isPalindrome(startIndex, endIndex - 1)) {
        path.push(s.slice(startIndex, endIndex));
        dfs(endIndex);
        path.pop();
      }
    }
  }

  dfs(0);
  return result;
}