AlgoPressAppearance
0131-分割回文串
https://leetcode.cn/problems/palindrome-partitioning
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
思路【自己想的，切割没搞明白】
每个单独字符都是回文串 从2位开始，逐步增加位置，判断是否是回文，思考如何去重? 重点：主要是分割的方式没有搞明白
参考代码
csharp
public class Solution {
List<IList<string>> result = new List<IList<string>>();
private bool IsPalindrome(List<char> list){
if(list.Count == 0){
return false;
}
int left = 0;
int right = list.Count-1;
while(left < right){
if(list[left] != list[right]){
return false;
}
left++;
right--;
}
return true;
}
private string GetString(List<char> list){
string str = "";
for(int i=0; i<list.Count; i++){
str+=list[i];
}
return str;
}
private void dfs(string s, int length){
if(length > s.Length){
return;
}
List<string> pd = new List<string>();
for(int i=0; i<s.Length-length+1; i++){
int subLength = length;
if(i+subLength > s.Length){
subLength = s.Length - i;
}
string temp = s.Substring(i,subLength);
if(IsPalindrome(temp)){
list.Add(temp)
}
}
dfs(s,length+1);
}
public IList<IList<string>> Partition(string s) {
List<char> list = new List<char>();
dfs(s,1,list);
return result;
}
}
思路2：回溯
例如对于字符串abcdef： 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个.....。 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。 
切割的时候， for 循环横向切割， dfs 纵向切割。 比如 aab 横向切割 a, 或者 aa， 或者 aab ，纵向切割从 切割完的地方开始。 因此需要 begin 所以
【总结】： 是因为切割很分解的思路一下子没考虑清楚，最开始考虑横向切割1个，1个， 然后两个两个。 这样递归的时候，很难处理，应该事先处理当前字符串的所有一次性的切法，然后剩下的递归处理。 需要利用递归的性质。
参考代码
csharp
public class Solution {
private List<IList<string>> result = new List<IList<string>>();
private bool IsPalindrome(string str){
if(str.Length == 1){
return true;
}
int left = 0;
int right = str.Length -1;
while(left < right){
if(str[left] != str[right]){
return false;
}
left++;
right--;
}
return true;
}
private List<string> CopyList(List<string> list){
List<string> newList = new List<string>();
for(int i=0; i<list.Count; i++){
newList.Add(list[i]);
}
return newList;
}
private void dfs(string s, int begin, List<string> list){
if(begin >= s.Length){
//输出结果
result.Add(CopyList(list));
return;
}
//横向遍历每一种长度的切法，然后剩余递归下面一步的切法
for(int i=begin; i<s.Length; i++){
string str = s.Substring(begin,i-begin+1);
if(IsPalindrome(str)){
list.Add(str);
//注意dfs这里传入的是i
dfs(s,i+1,list);
list.RemoveAt(list.Count - 1);
}
}
}
public IList<IList<string>> Partition(string s) {
List<string> list = new List<string>();
dfs(s,0,list);
return result;
}
}
复习：20220512
csharp
public class Solution {
List<IList<string>> result = new List<IList<string>>();
private bool IsPalindrome(string str){
int left = 0;
int right = str.Length-1;
while(left < right){
if(str[left] != str[right]){
return false;
}
left++;
right--;
}
return true;
}
private void dfs(string s, int begin, List<string> list){
//退出
if(begin == s.Length){
result.Add(new List<string>(list));
return;
}
//切割问题，横向for循环
for(int i=begin; i<s.Length; i++){
string str = s.Substring(begin,i-begin+1);
if(IsPalindrome(str)){
list.Add(str);
dfs(s,i+1,list);
list.RemoveAt(list.Count-1);
}
}
}
public IList<IList<string>> Partition(string s) {
List<string> list = new List<string>();
dfs(s,0,list);
return result;
}
}
复习：20220619
注意，横向切割的长度是 i-begin+1, 即 s.Substring(begin,i-begin+1)
csharp
public class Solution {
private List<IList<string>> result = new List<IList<string>>();
private bool isPalindrome(string str){
int left = 0;
int right = str.Length-1;
while(left < right){
if(str[left] != str[right]){
return false;
}
left++;
right--;
}
return true;
}
private void dfs(string s, int begin, List<string> list){
if(begin == s.Length){ //输出
result.Add(new List<string>(list.ToArray()));
return;
}
for(int i=begin; i<s.Length; i++){
string str = s.Substring(begin,i-begin+1);
if(isPalindrome(str)){
list.Add(str);
dfs(s,i+1,list);
list.RemoveAt(list.Count-1);
}
}
}
public IList<IList<string>> Partition(string s) {
//分隔方案，遍历各个长度切割到最后
List<string> list = new List<string>();
dfs(s,0,list);
return result;
}
}