做了两道回溯的题目，弄半天，。。。。。剪枝还减的很垃圾，勉强AC了。以后再看看。。。
131. 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
class Solution {
List<List<String>> res=new ArrayList<>();
List<Integer> point=new ArrayList<>();
public List<List<String>> partition(String s) {
helper(s,0);
return res;
}
public void helper(String s,int index)
{
if(index==s.length())
{
List<String> temp=isCorrect(s);
if(temp!=null)
res.add(temp);
point.remove(point.size()-1);
return ;
}
for(;index<s.length();index++)
{
int last=0;
if(point.size()>0)
last=point.get(point.size()-1);
String str=s.substring(last,index+1);
if(isRight(str))
{
point.add(index+1);
helper(s,index+1);
}
}
if(!point.isEmpty())
point.remove(point.size()-1);
return ;
}
public List<String> isCorrect(String s)
{
List<String> list=new ArrayList<>();
int l=0;
int r=0;
for(int i=0;i<point.size();i++)
{
r=point.get(i);
if(l==r)
return null;
String str=s.substring(l,r);
if(isRight(str))
list.add(str);
else
return null;
l=r;
}
return list;
}
public boolean isRight(String str)
{
for(int i=0;i<str.length()/2;i++)
{
if(str.charAt(i)!=str.charAt(str.length()-1-i))
return false;
}
return true;
}
}
93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
class Solution {
private int[] num=new int[3];
private List<String> list=new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if(s.length()==0)
return list;
if(s.length()>12)
return list;
helper(s,0,0);
return list;
}
public void helper(String s,int index,int count)
{
if(count==3)
{
String temp=isRight(s);
if(temp!=null)
list.add(temp);
return ;
}
for(;index<s.length();index++)
{
num[count]=index+1;
helper(s,index+1,count+1);
}
return ;
}
public String isRight(String s)
{
int l=0;
int r=0;
String string="";
if(num[2]>=s.length())
return null;
for(int i=0;i<3;i++)
{
r=num[i];
if(r-l>3||r==l)
return null;
if(r-l>1&&s.charAt(l)=='0')
return null;
String str=s.substring(l,r);
int value=Integer.parseInt(str);
if(value>255)
return null;
else
{
string+=str+".";
}
l=r;
}
r=s.length();
if(r-l>3||r==l)
return null;
if(r-l>1&&s.charAt(l)=='0')
return null;
String str=s.substring(l,r);
int value=Integer.parseInt(str);
if(value>255)
return null;
else
{
string+=str;
}
return string;
}
}