Palindrome partitioning

String Dynamic Programming Backtracking

73.7% acceptance

Jan 12, 2026

14194

569

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn partition_palindrome(s: String) -> Vec<Vec<String>> {
    let mut result = vec![];
    let mut current = vec![];
    Self::partition_backtrack(&s, 0, &mut current, &mut result);
    result
  }
  
  fn partition_backtrack(s: &str, start: usize, current: &mut Vec<String>, result: &mut Vec<Vec<String>>) {
    if start == s.len() {
      result.push(current.clone());
      return;
    }
    
    for end in start + 1..=s.len() {
      let substr = &s[start..end];
      if Self::partition_is_palindrome(substr) {
        current.push(substr.to_string());
        Self::partition_backtrack(s, end, current, result);
        current.pop();
      }
    }
  }
  
  fn partition_is_palindrome(s: &str) -> bool {
    let chars: Vec<char> = s.chars().collect();
    let mut left = 0;
    let mut right = chars.len();
    
    while left < right {
      right -= 1;
      if chars[left] != chars[right] {
        return false;
      }
      left += 1;
    }
    true
  }
}