131. Palindrome Partitioning – Leetcode Solutions

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def is_palindrome(sub: str) -> bool:
            """Check if a given string is a palindrome."""
            return sub == sub[::-1]

        def backtrack(start: int, path: List[str]):
            """
            Backtrack to find all possible palindrome partitions.
            start: the starting index for the current partition.
            path: the current list of palindromic substrings.
            """
            if start == len(s):
                # If we've reached the end of the string, add the current path to the result.
                result.append(path[:])
                return
            
            for end in range(start + 1, len(s) + 1):
                current_sub = s[start:end]
                if is_palindrome(current_sub):
                    # If the current substring is a palindrome, add it to the path and recurse.
                    path.append(current_sub)
                    backtrack(end, path)
                    # Backtrack by removing the last element added to the path.
                    path.pop()

        result = []
        backtrack(0, [])
        return result

/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    /**
     * Helper function to check if a given string is a palindrome.
     * @param {string} sub - The substring to check.
     * @return {boolean} - True if the substring is a palindrome, false otherwise.
     */
    function isPalindrome(sub) {
        return sub === sub.split('').reverse().join('');
    }

    /**
     * Backtrack function to find all possible palindrome partitions.
     * @param {number} start - The starting index for the current partition.
     * @param {string[]} path - The current list of palindromic substrings.
     */
    function backtrack(start, path) {
        // If we've reached the end of the string, add the current path to the result.
        if (start === s.length) {
            result.push([...path]);
            return;
        }

        // Try to partition the string by checking each substring.
        for (let end = start + 1; end <= s.length; end++) {
            let currentSub = s.slice(start, end);
            if (isPalindrome(currentSub)) {
                // If the current substring is a palindrome, add it to the path and recurse.
                path.push(currentSub);
                backtrack(end, path);
                // Backtrack by removing the last element added to the path.
                path.pop();
            }
        }
    }

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

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    /**
     * Helper function to check if a given string is a palindrome.
     * @param s - The string to check.
     * @param left - The starting index of the substring to check.
     * @param right - The ending index of the substring to check.
     * @return boolean - True if the substring is a palindrome, false otherwise.
     */
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /**
     * Backtrack function to find all possible palindrome partitions.
     * @param s - The input string.
     * @param start - The starting index for the current partition.
     * @param path - The current list of palindromic substrings.
     * @param result - The list to store all possible palindrome partitions.
     */
    private void backtrack(String s, int start, List<String> path, List<List<String>> result) {
        if (start == s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, result);
                path.remove(path.size() - 1);
            }
        }
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<string>> Partition(string s) {
        var result = new List<IList<string>>();
        Backtrack(s, 0, new List<string>(), result);
        return result;
    }

    /// <summary>
    /// Helper function to check if a given string is a palindrome.
    /// </summary>
    /// <param name="s">The string to check.</param>
    /// <param name="left">The starting index of the substring to check.</param>
    /// <param name="right">The ending index of the substring to check.</param>
    /// <returns>True if the substring is a palindrome, false otherwise.</returns>
    private bool IsPalindrome(string s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    /// <summary>
    /// Backtrack function to find all possible palindrome partitions.
    /// </summary>
    /// <param name="s">The input string.</param>
    /// <param name="start">The starting index for the current partition.</param>
    /// <param name="path">The current list of palindromic substrings.</param>
    /// <param name="result">The list to store all possible palindrome partitions.</param>
    private void Backtrack(string s, int start, List<string> path, List<IList<string>> result) {
        if (start == s.Length) {
            result.Add(new List<string>(path));
            return;
        }

        for (int end = start; end < s.Length; end++) {
            if (IsPalindrome(s, start, end)) {
                path.Add(s.Substring(start, end - start + 1));
                Backtrack(s, end + 1, path, result);
                path.RemoveAt(path.Count - 1);
            }
        }
    }
}