45 回溯算法解分割回文串

问题描述：给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串，返回s所有可能的分割方案；回溯算法求解：对于dfs函数定义一个index表明当前所在的位置，并以该位置为起点分别进行往后遍历，要是index和遍历位置是回文子串，则添加进入templist中，并进入下一个dfs中，当这个dfs退出来之后，去除templist的元素，并进行下一个循环的判断。
?

public Boolean isPalindrome(String s)
{
int start=0;
int end=s.length()-1;
while(end>start)
{
if(s.charAt(start)!=s.charAt(end))
{
return false;
}
end--;
start++;
}
???????return true;
}

public traceBack(String s,index,LinkedList<String>templist,LinkedList<LinkedList<String>>res)
{
if(index==s.length())
{
res.add(templist);
return;
}
for(int i=index;i<s,length();i++)
{
if(isPalindrome(s.substring(index,i+1)))
{
templist.add(s.substring(index,i+1));
traceback(s,i+1,templist,res);
templist.remove(templist.size()-1);
}else
{
continue;
}
}
}
public LinkedList<LinkedList<String>> DFS(String s)
{
LinkedList<LinkedList<String>>res=new?LinkedList<LinkedList<String>>();
tranceBack(s,0,new ArrayList<String>(),res);
???????return res;
}