LeetCode //C - 131. Palindrome Partitioning

本文主要是介绍LeetCode //C - 131. Palindrome Partitioning，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

131. Palindrome Partitioning

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

Example 1:

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

Example 2:

Input: s = “a”
Output: [[“a”]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

From: LeetCode
Link: 131. Palindrome Partitioning

Solution:

Ideas：

Exploration of Partitions: Starting from the beginning of the string, the code explores all possible ways to partition the string into substrings. It does this by iteratively increasing the end index of a potential partition and checking if the substring formed is a palindrome.
Checking for Palindromes: For each potential partition, it checks whether the substring is a palindrome. This is done using the isPalindrome function, which compares characters from the start and end of the substring moving towards the center.
Backtracking: If a substring is a palindrome, it is added to the current “path” (a list of substrings that are all palindromes). The function then recursively explores further partitions of the remainder of the string. If the end of the string is reached, it means a valid partitioning has been found, and it is added to the result list.
Recording Results: Once a valid partitioning that reaches the end of the string is found, this partitioning is saved as part of the results. The “path” at this point represents a set of substrings that are all palindromes and collectively partition the entire string.

Code:

bool isPalindrome(char* s, int start, int end) {while (start < end) {if (s[start++] != s[end--]) return false;}return true;
}void backtrack(char* s, int start, int len, char*** result, int* returnSize, int** returnColumnSizes, char** path, int pathSize) {if (start == len) {// Allocate memory for a partition and copy the path into itresult[*returnSize] = (char**)malloc(pathSize * sizeof(char*));for (int i = 0; i < pathSize; i++) {result[*returnSize][i] = strdup(path[i]);}(*returnColumnSizes)[*returnSize] = pathSize;(*returnSize)++;return;}for (int end = start; end < len; end++) {if (isPalindrome(s, start, end)) {// Extract the palindrome substringint substrLen = end - start + 1;char* substr = (char*)malloc((substrLen + 1) * sizeof(char));strncpy(substr, s + start, substrLen);substr[substrLen] = '\0';  // Null-terminate the substring// Add this substring to the path and continuepath[pathSize] = substr;backtrack(s, end + 1, len, result, returnSize, returnColumnSizes, path, pathSize + 1);// Backtrack: remove the substring from the pathfree(substr);}}
}char*** partition(char* s, int* returnSize, int** returnColumnSizes) {int len = strlen(s);char*** result = (char***)malloc(sizeof(char**) * (1 << len)); // Enough space for all combinations*returnColumnSizes = (int*)malloc(sizeof(int) * (1 << len));char** path = (char**)malloc(len * sizeof(char*)); // Temporary storage for current partition path*returnSize = 0;backtrack(s, 0, len, result, returnSize, returnColumnSizes, path, 0);free(path);return result;
}