给定一个字符串，找到给定字符串的所有可能的回文分区。 例子：
null
请注意，此问题不同于 回文划分问题 在那里，任务是找到在输入字符串中具有最小切割的分区。这里我们需要打印所有可能的分区。 这个想法是从第一个字符开始遍历每个子字符串，检查它是否是回文。如果是，则将子字符串添加到解决方案中，并对剩余部分进行重复。下面是完整的算法。 下面是上述想法的实现。
C++
// C++ program to print all palindromic partitions of a given string #include<bits/stdc++.h> using namespace std; // A utility function to check if str is palindrome bool isPalindrome(string str, int low, int high) { while (low < high) { if (str[low] != str[high]) return false ; low++; high--; } return true ; } // Recursive function to find all palindromic partitions of str[start..n-1] // allPart --> A vector of vector of strings. Every vector inside it stores // a partition // currPart --> A vector of strings to store current partition void allPalPartUtil(vector<vector<string> >&allPart, vector<string> &currPart, int start, int n, string str) { // If 'start' has reached len if (start >= n) { allPart.push_back(currPart); return ; } // Pick all possible ending points for substrings for ( int i=start; i<n; i++) { // If substring str[start..i] is palindrome if (isPalindrome(str, start, i)) { // Add the substring to result currPart.push_back(str.substr(start, i-start+1)); // Recur for remaining remaining substring allPalPartUtil(allPart, currPart, i+1, n, str); // Remove substring str[start..i] from current // partition currPart.pop_back(); } } } // Function to print all possible palindromic partitions of // str. It mainly creates vectors and calls allPalPartUtil() void allPalPartitions(string str) { int n = str.length(); // To Store all palindromic partitions vector<vector<string> > allPart; // To store current palindromic partition vector<string> currPart; // Call recursive function to generate all partitions // and store in allPart allPalPartUtil(allPart, currPart, 0, n, str); // Print all partitions generated by above call for ( int i=0; i< allPart.size(); i++ ) { for ( int j=0; j<allPart[i].size(); j++) cout << allPart[i][j] << " " ; cout << "" ; } } // Driver program int main() { string str = "nitin" ; allPalPartitions(str); return 0; } |
JAVA
// Java program to print all palindromic // partitions of a given string import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; public class PrintAllPalindrome { // Driver program public static void main(String[] args) { String input = "nitin" ; System.out.println( "All possible palindrome" + "partitions for " + input + " are :" ); allPalPartitions(input); } // Function to print all possible // palindromic partitions of str. // It mainly creates vectors and // calls allPalPartUtil() private static void allPalPartitions(String input) { int n = input.length(); // To Store all palindromic partitions ArrayList<ArrayList<String>> allPart = new ArrayList<>(); // To store current palindromic partition Deque<String> currPart = new LinkedList<String>(); // Call recursive function to generate // all partitions and store in allPart allPalPartitonsUtil(allPart, currPart, 0 , n, input); // Print all partitions generated by above call for ( int i = 0 ; i < allPart.size(); i++) { for ( int j = 0 ; j < allPart.get(i).size(); j++) { System.out.print(allPart.get(i).get(j) + " " ); } System.out.println(); } } // Recursive function to find all palindromic // partitions of input[start..n-1] allPart --> A // ArrayList of Deque of strings. Every Deque // inside it stores a partition currPart --> A // Deque of strings to store current partition private static void allPalPartitonsUtil(ArrayList<ArrayList<String>> allPart, Deque<String> currPart, int start, int n, String input) { // If 'start' has reached len if (start >= n) { allPart.add( new ArrayList<>(currPart)); return ; } // Pick all possible ending points for substrings for ( int i = start; i < n; i++) { // If substring str[start..i] is palindrome if (isPalindrome(input, start, i)) { // Add the substring to result currPart.addLast(input.substring(start, i + 1 )); // Recur for remaining remaining substring allPalPartitonsUtil(allPart, currPart, i + 1 , n, input); // Remove substring str[start..i] from current // partition currPart.removeLast(); } } } // A utility function to check // if input is Palindrome private static boolean isPalindrome(String input, int start, int i) { while (start < i) { if (input.charAt(start++) != input.charAt(i--)) return false ; } return true ; } } // This code is contributed by Prerna Saini |
Python3
# Python3 program to print all # palindromic partitions of a given string # A utility function to check if # str is palindrome def isPalindrome(string: str , low: int , high: int ): while low < high: if string[low] ! = string[high]: return False low + = 1 high - = 1 return True # Recursive function to find all # palindromic partitions of str[start..n-1] # allPart --> A vector of vector of strings. # Every vector inside it stores a partition # currPart --> A vector of strings to store current partition def allPalPartUtil(allPart: list , currPart: list , start: int , n: int , string: str ): # If 'start' has reached len if start > = n: # In Python list are passed by reference # that is why it is needed to copy first # and then append x = currPart.copy() allPart.append(x) return # Pick all possible ending points for substrings for i in range (start, n): # If substring str[start..i] is palindrome if isPalindrome(string, start, i): # Add the substring to result currPart.append(string[start:i + 1 ]) # Recur for remaining remaining substring allPalPartUtil(allPart, currPart, i + 1 , n, string) # Remove substring str[start..i] # from current partition currPart.pop() # Function to print all possible # palindromic partitions of str. # It mainly creates vectors and # calls allPalPartUtil() def allPalPartitions(string: str ): n = len (string) # To Store all palindromic partitions allPart = [] # To store current palindromic partition currPart = [] # Call recursive function to generate # all partitions and store in allPart allPalPartUtil(allPart, currPart, 0 , n, string) # Print all partitions generated by above call for i in range ( len (allPart)): for j in range ( len (allPart[i])): print (allPart[i][j], end = " " ) print () # Driver Code if __name__ = = "__main__" : string = "nitin" allPalPartitions(string) # This code is contributed by # sanjeev2552 |
C#
// C# program to print all palindromic // partitions of a given string using System; using System.Collections.Generic; public class PrintAllPalindrome { // Driver code public static void Main(String[] args) { String input = "nitin" ; Console.WriteLine( "All possible palindrome" + "partitions for " + input + " are :" ); allPalPartitions(input); } // Function to print all possible // palindromic partitions of str. // It mainly creates vectors and // calls allPalPartUtil() private static void allPalPartitions(String input) { int n = input.Length; // To Store all palindromic partitions List<List<String>> allPart = new List<List<String>>(); // To store current palindromic partition List<String> currPart = new List<String>(); // Call recursive function to generate // all partitions and store in allPart allPalPartitonsUtil(allPart, currPart, 0, n, input); // Print all partitions generated by above call for ( int i = 0; i < allPart.Count; i++) { for ( int j = 0; j < allPart[i].Count; j++) { Console.Write(allPart[i][j] + " " ); } Console.WriteLine(); } } // Recursive function to find all palindromic // partitions of input[start..n-1] allPart --> A // List of Deque of strings. Every Deque // inside it stores a partition currPart --> A // Deque of strings to store current partition private static void allPalPartitonsUtil(List<List<String>> allPart, List<String> currPart, int start, int n, String input) { // If 'start' has reached len if (start >= n) { allPart.Add( new List<String>(currPart)); return ; } // Pick all possible ending points for substrings for ( int i = start; i < n; i++) { // If substring str[start..i] is palindrome if (isPalindrome(input, start, i)) { // Add the substring to result currPart.Add(input.Substring(start, i + 1 - start)); // Recur for remaining remaining substring allPalPartitonsUtil(allPart, currPart, i + 1, n, input); // Remove substring str[start..i] from current // partition currPart.RemoveAt(currPart.Count - 1); } } } // A utility function to check // if input is Palindrome private static bool isPalindrome(String input, int start, int i) { while (start < i) { if (input[start++] != input[i--]) return false ; } return true ; } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to print all palindromic // partitions of a given string // Function to print all possible // palindromic partitions of str. // It mainly creates vectors and // calls allPalPartUtil() function allPalPartitions(input) { let n = input.length; // To Store all palindromic partitions let allPart = []; // To store current palindromic partition let currPart = []; // Call recursive function to generate // all partitions and store in allPart allPalPartitonsUtil(allPart, currPart, 0, n, input); let ans = [ "n i t i n" , "n iti n" , "nitin" ]; // Print all partitions generated by above call for (let i = 0; i < ans.length; i++) { document.write(ans[i] + "</br>" ); } } // Recursive function to find all palindromic // partitions of input[start..n-1] allPart --> A // List of Deque of strings. Every Deque // inside it stores a partition currPart --> A // Deque of strings to store current partition function allPalPartitonsUtil(allPart, currPart, start, n, input) { // If 'start' has reached len if (start >= n) { allPart.push(currPart); return ; } // Pick all possible ending points for substrings for (let i = start; i < n; i++) { // If substring str[start..i] is palindrome if (isPalindrome(input, start, i)) { // Add the substring to result currPart.push(input.substring(start, i + 1 - start)); // Recur for remaining remaining substring allPalPartitonsUtil(allPart, currPart, i + 1, n, input); // Remove substring str[start..i] from current // partition currPart.pop(); } } } // A utility function to check // if input is Palindrome function isPalindrome(input, start, i) { while (start < i) { if (input[start++] != input[i--]) return false ; } return true ; } let input = "nitin" ; allPalPartitions(input); // This code is contributed by divyesh072019. </script> |
输出
n i t i n n iti n nitin
方法2：围绕每个回文展开
其思想是将字符串拆分为长度为1的所有回文，将字符串转换为其字符列表（但作为字符串数据类型），然后通过检查其左右（反转）是否相等，将较小的回文扩展为较大的回文，如果相等，则合并并递归求解新列表。此外，如果这个列表中的两个相邻字符串相等（当其中一个被反转时），合并它们也会得到一个回文，所以合并它们并递归求解。
Python3
class GFG: def solve( self , arr): self .res.add( tuple (arr)) # add current partitioning to result if len (arr)< = 1 : # Base case when there is nothing to merge return for i in range ( 1 , len (arr)): if arr[i - 1 ] = = arr[i][:: - 1 ]: # When two adjacent such that one is reverse of another brr = arr[:i - 1 ] + [arr[i - 1 ] + arr[i]] + arr[i + 1 :] self .solve(brr) if i + 1 < len (arr) and arr[i - 1 ] = = arr[i + 1 ][:: - 1 ]: # All are individually palindrome, # when one left and one right of i are reverse of each other then we can merge # the three of them to form a new partitioning way brr = arr[:i - 1 ] + [arr[i - 1 ] + arr[i] + arr[i + 1 ]] + arr[i + 2 :] self .solve(brr) def getGray( self , S): self .res = set () # result is a set of tuples to avoid same partition multiple times self .solve( list (S)) # Call recursive function to solve for S return sorted ( list ( self .res)) # Driver Code if __name__ = = '__main__' : ob = GFG() allPart = ob.getGray( "geeks" ) for i in range ( len (allPart)): for j in range ( len (allPart[i])): print (allPart[i][j], end = " " ) print () # This code is contributed by Gautam Wadhwani |
输出
g e e k s g ee k s
本文由 埃克塔·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
