Palindrome Partitioning

                                            
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> currentList;
        backtrack(result, s, 0, currentList);
        return result;
    }
    
    void backtrack(vector<vector<string>>& result, string s, int start, vector<string>& currentList) {
        if (start >= s.length()) {
            result.push_back(currentList);
            return;
        }
        
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                currentList.push_back(s.substr(start, end - start + 1));
                backtrack(result, s, end + 1, currentList);
                currentList.pop_back();
            }
        }
    }
    
    bool isPalindrome(string s, int start, int end) {
        while (start < end) {
            if (s[start] != s[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
};

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

    private void backtrack(List<List<String>> result, List<String> tempList, String s, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i < s.length(); i++) {
                if (isPalindrome(s, start, i)) {
                    tempList.add(s.substring(start, i + 1));
                    backtrack(result, tempList, s, i + 1);
                    tempList.remove(tempList.size() - 1);
                }
            }
        }
    }

    private boolean isPalindrome(String s, int low, int high) {
        while (low < high) {
            if (s.charAt(low++) != s.charAt(high--)) {
                return false;
            }
        }
        return true;
    }
}

                                            
class Solution(object):
    def partition(self, s):
        def is_palindrome(s):
            return s == s[::-1]

        def backtrack(start, path):
            if start == len(s):
                res.append(path[:])
                return
            for end in range(start + 1, len(s) + 1):
                if is_palindrome(s[start:end]):
                    path.append(s[start:end])
                    backtrack(end, path)
                    path.pop()

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

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

    private void Backtrack(IList<IList<string>> result, List<string> tempList, string s, int start) {
        if (start == s.Length) {
            result.Add(new List<string>(tempList));
        } else {
            for (int i = start; i < s.Length; i++) {
                if (IsPalindrome(s, start, i)) {
                    tempList.Add(s.Substring(start, i - start + 1));
                    Backtrack(result, tempList, s, i + 1);
                    tempList.RemoveAt(tempList.Count - 1);
                }
            }
        }
    }

    private bool IsPalindrome(string s, int low, int high) {
        while (low < high) {
            if (s[low] != s[high]) {
                return false;
            }
            low++;
            high--;
        }
        return true;
    }
}

                                            
/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function(s) {
    const result = [];
    
    const isPalindrome = (str, start, end) => {
        while (start < end) {
            if (str[start] !== str[end]) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    };
    
    const backtrack = (startIndex, path) => {
        if (startIndex === s.length) {
            result.push([...path]);
            return;
        }
        
        for (let i = startIndex; i < s.length; i++) {
            if (isPalindrome(s, startIndex, i)) {
                path.push(s.substring(startIndex, i + 1));
                backtrack(i + 1, path);
                path.pop();
            }
        }
    };
    
    backtrack(0, []);
    
    return result;
};

                                            
function partition(s: string): string[][] {
    const result: string[][] = [];
    
    const isPalindrome = (str: string): boolean => {
        let left = 0;
        let right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    };
    
    const backtrack = (start: number, path: string[]) => {
        if (start === s.length) {
            result.push([...path]);
            return;
        }
        
        for (let end = start; end < s.length; end++) {
            const substring = s.substring(start, end + 1);
            if (isPalindrome(substring)) {
                path.push(substring);
                backtrack(end + 1, path);
                path.pop();
            }
        }
    };
    
    backtrack(0, []);
    
    return result;
};

                                            
class Solution {
    /**
     * @param String $s
     * @return String[][]
     */
    function partition($s) {
        $result = [];
        $current = [];
        $this->backtrack($result, $current, $s, 0);
        return $result;
    }

    function backtrack(&$result, &$current, $s, $start) {
        if ($start == strlen($s)) {
            $result[] = $current;
            return;
        }
        
        for ($i = $start; $i < strlen($s); $i++) {
            if ($this->isPalindrome($s, $start, $i)) {
                $substring = substr($s, $start, $i - $start + 1);
                $current[] = $substring;
                $this->backtrack($result, $current, $s, $i + 1);
                array_pop($current);
            }
        }
    }

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

                                            
class Solution {
    func partition(_ s: String) -> [[String]] {
        var result = [[String]]()
        var currentList = [String]()
        
        backtrack(&result, Array(s), 0, &currentList)
        
        return result
    }
    
    private func backtrack(_ result: inout [[String]], _ sArr: [Character], _ start: Int, _ currentList: inout [String]) {
        if start == sArr.count {
            result.append(currentList)
            return
        }
        
        for end in start..<sArr.count {
            if isPalindrome(sArr, start, end) {
                let substring = String(sArr[start...end])
                currentList.append(substring)
                backtrack(&result, sArr, end + 1, &currentList)
                currentList.removeLast()
            }
        }
    }
    
    private func isPalindrome(_ sArr: [Character], _ left: Int, _ right: Int) -> Bool {
        var l = left
        var r = right
        
        while l < r {
            if sArr[l] != sArr[r] {
                return false
            }
            l += 1
            r -= 1
        }
        
        return true
    }
}

                                            
class Solution {
    fun partition(s: String): List<List<String>> {
        val result = mutableListOf<List<String>>()
        backtrack(s, 0, mutableListOf(), result)
        return result
    }
    
    private fun backtrack(s: String, start: Int, path: MutableList<String>, result: MutableList<List<String>>) {
        if (start == s.length) {
            result.add(ArrayList(path))
            return
        }
        
        for (i in start until s.length) {
            if (isPalindrome(s, start, i)) {
                path.add(s.substring(start, i + 1))
                backtrack(s, i + 1, path, result)
                path.removeAt(path.size - 1)
            }
        }
    }
    
    private fun isPalindrome(s: String, low: Int, high: Int): Boolean {
        var i = low
        var j = high
        while (i < j) {
            if (s[i] != s[j]) {
                return false
            }
            i++
            j--
        }
        return true
    }
}

                                            
class Solution {
  List<List<String>> partition(String s) {
    List<List<String>> result = [];
    List<String> currentList = [];
    backtrack(result, s, 0, currentList);
    return result;
  }

  void backtrack(List<List<String>> result, String s, int start, List<String> currentList) {
    if (start == s.length) {
      result.add(List.from(currentList));
      return;
    }

    for (int i = start; i < s.length; i++) {
      if (isPalindrome(s, start, i)) {
        currentList.add(s.substring(start, i + 1));
        backtrack(result, s, i + 1, currentList);
        currentList.removeLast();
      }
    }
  }

  bool isPalindrome(String s, int low, int high) {
    while (low < high) {
      if (s[low] != s[high]) {
        return false;
      }
      low++;
      high--;
    }
    return true;
  }
}

                                            
func partition(s string) [][]string {
    var result [][]string
    var path []string
    backtrack(&result, path, s, 0)
    return result
}

func backtrack(result *[][]string, path []string, s string, idx int) {
    if idx == len(s) {
        temp := make([]string, len(path))
        copy(temp, path)
        *result = append(*result, temp)
        return
    }
    
    for i := idx; i < len(s); i++ {
        if isPalindrome(s, idx, i) {
            path = append(path, s[idx:i+1])
            backtrack(result, path, s, i+1)
            path = path[:len(path)-1]
        }
    }
}

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

                                            
# @param {String} s
# @return {String[][]}
def partition(s)
    result = []
    backtrack(s, 0, [], result)
    result
end

def backtrack(s, start, path, result)
    if start == s.length
        result << path.dup
        return
    end
    
    (start...s.length).each do |i|
        if is_palindrome(s, start, i)
            path << s[start..i]
            backtrack(s, i + 1, path, result)
            path.pop
        end
    end
end

def is_palindrome(s, low, high)
    while low < high
        return false if s[low] != s[high]
        low += 1
        high -= 1
    end
    true
end

                                            
object Solution {
    def partition(s: String): List[List[String]] = {
        def isPalindrome(str: String): Boolean = {
            str == str.reverse
        }
        
        def backtrack(start: Int, current: List[String]): List[List[String]] = {
            if (start >= s.length) {
                List(current)
            } else {
                (start until s.length).flatMap(end => {
                    val substring = s.substring(start, end + 1)
                    if (isPalindrome(substring)) {
                        backtrack(end + 1, current :+ substring)
                    } else {
                        List()
                    }
                }).toList
            }
        }
        
        backtrack(0, List())
    }
}

                                            
impl Solution {
    pub fn partition(s: String) -> Vec<Vec<String>> {
        fn is_palindrome(s: &str) -> bool {
            let n = s.len();
            let s = s.as_bytes();
            let mut dp = vec![vec![false; n]; n];
            
            for i in 0..n {
                dp[i][i] = true;
            }
            
            for len in 2..=n {
                for i in 0..n-len+1 {
                    let j = i + len - 1;
                    if len == 2 {
                        dp[i][j] = s[i] == s[j];
                    } else {
                        dp[i][j] = s[i] == s[j] && dp[i+1][j-1];
                    }
                }
            }
            
            dp[0][n-1]
        }
        
        fn backtrack(s: &str, start: usize, path: &mut Vec<String>, res: &mut Vec<Vec<String>>) {
            if start == s.len() {
                res.push(path.clone());
                return;
            }
            
            for end in start..s.len() {
                let substr = &s[start..=end];
                if is_palindrome(substr) {
                    path.push(substr.to_string());
                    backtrack(s, end + 1, path, res);
                    path.pop();
                }
            }
        }
        
        let mut res = Vec::new();
        let mut path = Vec::new();
        
        backtrack(&s, 0, &mut path, &mut res);
        
        res
    }
}

To solve this coding challenge, we need to partition the given string

s

such that every substring of the partition is a palindrome. We should return all possible palindrome partitionings of

s

Explanation:

To approach this problem, we can use a backtracking algorithm. Backtracking helps us explore all potential partitions and verify if they form palindromes. Here’s the step-by-step breakdown:

Base Requirements :

We need to generate all possible partitions of the string
s

.
Each partition should only contain substrings which are palindromes.

Recursive Backtracking Strategy :

We use recursion to explore potential partitions starting from the beginning of the string.
For each position in the string
s

, we check for every possible end position if the substring from the start to this end is a palindrome.
If it is a palindrome, we add it to the current path and recursively attempt to partition the remaining substring.
If we reach the end of the string, we add the current path to the list of valid palindrome partitionings.

Palindrome Check :

A helper function to check if a given substring is a palindrome. This is done by comparing the substring to its reverse.

Backtracking Helper :

This function uses a starting index and continuously tries to extend the end index to find palindromic substrings, then recurses to check for further partitions from the new start index.

Result Collection :

When the start index reaches the length of the string, it indicates that we've successfully partitioned the entire string.

Here is the pseudocode including comments for better understanding:

                                            
# Check if the substring is a palindrome
function is_palindrome(substring):
return substring is equal to reverse(substring)

# Backtracking function to find palindromic partitions
function backtrack(start_index, current_path, s, result):
if start_index is equal to length of s:
# If start_index reaches the end, we add the current path to result
append current_path copy to result
return

# Try to partition the string from start_index to all possible end_indices
for end_index from start_index + 1 to length of s + 1:
substring = s from start_index to end_index
if is_palindrome(substring):
# If the substring is a palindrome, add it to current path
append substring to current_path
# Recurse to partition the remaining substring
backtrack(end_index, current_path, s, result)
# Backtrack by removing the last added substring
remove last element from current_path

# Main function to initiate partition process
function partition(s):
result = empty list
backtrack(0, empty list, s, result)
return result

# Example input and expected output
input_s_1 = "aab"
output_1 = [["a", "a", "b"], ["aa", "b"]]

input_s_2 = "a"
output_2 = [["a"]]

print(partition(input_s_1)) # Expected: [["a", "a", "b"], ["aa", "b"]]
print(partition(input_s_2)) # Expected: [["a"]]

Detailed Steps in Pseudocode

Check if a substring is a palindrome :

Function
is_palindrome(substring)

compares the substring with its reverse. If both are equal, it returns true indicating that it is a palindrome.

Backtracking Function :

The
backtrack

function accepts four parameters: the current starting index
start_index

, the current partition path
current_path

, the original string
s

, and the collection list
result

.
If
start_index

equals the length of
s

, it means we have explored one valid partition; thus, we copy
current_path

to
result

.
For every possible end index from
start_index + 1

to the length of
s

, we extract the substring from
start_index

to
end_index

.
If this substring is a palindrome, it's added to
current_path

, and we recursively call
backtrack

with the new start index of
end_index

.
Following the recursion, we remove the last added substring to backtrack and try other possibilities.

Main Function :

The main function
partition(s)

initializes an empty
result

list and calls the
backtrack

function starting at index 0 with an empty
current_path

.
Finally, it returns the
result

which contains all the valid palindrome partitionings of
s

.

By implementing these functions recursively, we can ensure that all possible palindrome partitions are explored and collected. This method guarantees that the solution covers all potential partitions by backtracking through every possible partitioning path.