给定一个字符串s，分区s的每个字符串都是回文。返回s的所有可能回文分区。
null
例子：
Input : s = "bcc"
Output : [["b", "c", "c"], ["b", "cc"]]
Input : s = "geeks"
Output : [["g", "e", "e", "k", "s"],
["g", "ee", "k", "s"]]
我们必须列出所有可能的分区，这样我们才能朝着递归的方向思考。当我们在索引i上时，我们递增地检查从i开始的所有子串是否是回文的。如果找到，我们递归地解决剩余字符串的问题，并将其添加到我们的解决方案中。
以下是解决方案-
- 我们将维护一个用于存储所有可能分区的二维向量和一个用于存储当前分区的临时向量，新的字符串起始索引用于检查分区，因为我们已经在该索引之前检查了分区。
- 现在继续在字符串上进一步迭代，检查它是否是回文。
- 如果是回文，则将该字符串添加到当前分区向量中。如果新字符串不是字符串的结尾，则在该字符串上递归。再次返回后，将当前分区向量更改为旧分区向量，因为它可能在递归步骤中发生了更改。
- 如果我们在迭代时到达字符串的末尾，那么我们的临时向量中就有了分区，所以我们将在结果中添加它。
要检查它是否是回文，请使用两个指针对字符串进行迭代。初始化字符串的开头和结尾。如果两个字符相同，则增加第一个指针，减少最后一个指针，并继续迭代，直到第一个指针小于最后一个指针。
C++
// C++ program to print all palindromic partitions // of a given string. #include <bits/stdc++.h> using namespace std; // Returns true if str is palindrome, else false bool checkPalindrome(string str) { int len = str.length(); len--; for ( int i=0; i<len; i++) { if (str[i] != str[len]) return false ; len--; } return true ; } void printSolution(vector<vector<string> > partitions) { for ( int i = 0; i < partitions.size(); ++i) { for ( int j = 0; j < partitions[i].size(); ++j) cout << partitions[i][j] << " " ; cout << endl; } return ; } // Goes through all indexes and recursively add remaining // partitions if current string is palindrome. void addStrings(vector<vector<string> > &v, string &s, vector<string> &temp, int index) { int len = s.length(); string str; vector<string> current = temp; if (index == 0) temp.clear(); for ( int i = index; i < len; ++i) { str = str + s[i]; if (checkPalindrome(str)) { temp.push_back(str); if (i+1 < len) addStrings(v,s,temp,i+1); else v.push_back(temp); temp = current; } } return ; } // Generates all palindromic partitions of 's' and // stores the result in 'v'. void partition(string s, vector<vector<string> >&v) { vector<string> temp; addStrings(v, s, temp, 0); printSolution(v); return ; } // Driver code int main() { string s = "geeks" ; vector<vector<string> > partitions; partition(s, partitions); return 0; } |
JAVA
// Java program to print all palindromic partitions // of a given string. import java.util.ArrayList; public class GFG { // Returns true if str is palindrome, else false static boolean checkPalindrome(String str) { int len = str.length(); len--; for ( int i= 0 ; i<len; i++) { if (str.charAt(i) != str.charAt(len)) return false ; len--; } return true ; } // Prints the partition list static void printSolution(ArrayList<ArrayList<String>> partitions) { for (ArrayList<String> i: partitions) { for (String j: i) { System.out.print(j+ " " ); } System.out.println(); } } // Goes through all indexes and recursively add remaining // partitions if current string is palindrome. static ArrayList<ArrayList<String>> addStrings(ArrayList< ArrayList<String>> v, String s, ArrayList<String> temp, int index) { int len = s.length(); String str = "" ; ArrayList<String> current = new ArrayList<>(temp); if (index == 0 ) temp.clear(); // Iterate over the string for ( int i = index; i < len; ++i) { str = str + s.charAt(i); // check whether the substring is // palindromic or not if (checkPalindrome(str)) { // if palindrome add it to temp list temp.add(str); if (i + 1 < len) { // recurr to get all the palindromic // partitions for the substrings v = addStrings(v,s,temp,i+ 1 ); } else { // if end of the string is reached // add temp to v v.add(temp); } // temp is reinitialize with the // current i. temp = new ArrayList<>(current); } } return v; } // Generates all palindromic partitions of 's' and // stores the result in 'v'. static void partition(String s, ArrayList<ArrayList< String>> v) { // temporary ArrayList to store each // palindromic string ArrayList<String> temp = new ArrayList<>(); // calling addString method it adds all // the palindromic partitions to v v = addStrings(v, s, temp, 0 ); // printing the solution printSolution(v); } // Driver code public static void main(String args[]) { String s = "geeks" ; ArrayList<ArrayList<String>> partitions = new ArrayList<>(); partition(s, partitions); } } // This code is contributed by Sumit Ghosh |
Python3
# Python3 program to print all palindromic # partitions of a given string. def checkPalindrome(string): # Returns true if str is palindrome, # else false length = len (string) length - = 1 for i in range (length): if string[i] ! = string[length]: return False length - = 1 return True def printSolution(partitions): for i in range ( len (partitions)): for j in range ( len (partitions[i])): print (partitions[i][j], end = " " ) print () def addStrings(v, s, temp, index): # Goes through all indexes and # recursively add remaining partitions # if current string is palindrome. length = len (s) string = "" current = temp[:] if index = = 0 : temp = [] for i in range (index, length): string + = s[i] if checkPalindrome(string): temp.append(string) if i + 1 < length: addStrings(v, s, temp[:], i + 1 ) else : v.append(temp) temp = current def partition(s, v): # Generates all palindromic partitions # of 's' and stores the result in 'v'. temp = [] addStrings(v, s, temp[:], 0 ) printSolution(v) # Driver Code if __name__ = = "__main__" : s = "geeks" partitions = [] partition(s, partitions) # This code is contributed by # vibhu4agarwal |
C#
// C# program to print all palindromic partitions // of a given string. using System; using System.Collections.Generic; class GFG { // Returns true if str is palindrome, else false static bool checkPalindrome(String str) { int len = str.Length; len--; for ( int i = 0; i < len; i++) { if (str[i] != str[len]) return false ; len--; } return true ; } // Prints the partition list static void printSolution(List<List<String>> partitions) { foreach (List<String> i in partitions) { foreach (String j in i) { Console.Write(j+ " " ); } Console.WriteLine(); } } // Goes through all indexes and recursively add remaining // partitions if current string is palindrome. static List<List<String>> addStrings(List< List<String>> v, String s, List<String> temp, int index) { int len = s.Length; String str = "" ; List<String> current = new List<String>(temp); if (index == 0) temp.Clear(); // Iterate over the string for ( int i = index; i < len; ++i) { str = str + s[i]; // check whether the substring is // palindromic or not if (checkPalindrome(str)) { // if palindrome add it to temp list temp.Add(str); if (i + 1 < len) { // recurr to get all the palindromic // partitions for the substrings v = addStrings(v,s,temp,i+1); } else { // if end of the string is reached // add temp to v v.Add(temp); } // temp is reinitialize with the // current i. temp = new List<String>(current); } } return v; } // Generates all palindromic partitions of 's' and // stores the result in 'v'. static void partition(String s, List<List< String>> v) { // temporary List to store each // palindromic string List<String> temp = new List<String>(); // calling addString method it adds all // the palindromic partitions to v v = addStrings(v, s, temp, 0); // printing the solution printSolution(v); } // Driver code public static void Main(String []args) { String s = "geeks" ; List<List<String>> partitions = new List<List<String>>(); partition(s, partitions); } } // This code is contributed by PrinciRaj1992 |
输出：
g e e k s g ee k s
相关文章： 动态规划|集17（回文划分）
本文由 安舒尔·戈亚尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
