剑指 Offer II 回溯法

086. 分割回文子字符串

用substr枚举 因为是连续的 不是放与不放的问题

class Solution {
public:
vector>ans;
vectorpath;
bool check()
{
    for(string x:path)
    {
        for(int i=0;i> partition(string s) {
        dfs(0,s);
        return ans;

    }
};

087. 复原 IP

剪枝

class Solution {
public:
 vectorans;
  vectorpath;
  int tonum(string x)
  {
      int sum=0;
      for(int i=0;i3)return false;
         if(x.size()>1&&x[0]=='0')return false;//前导0
         if(tonum(x)>255)return false;//IP

     }
     return true;

 }
 void dfs(int x, string s)
 {
     if(x==s.size())
     {
         if(path.size()!=4)return ;
         if(check())
         {
             string k;
             for(string x:path)
             {
                 k+=x;
                 k+=".";
             }
             k=k.substr(0,k.size()-1);
             ans.push_back(k);
         }
     }
     for(int i=1;i<=s.size()-x;i++)
     {
         string temp=s.substr(x,i);//以x为起点 长度为i的字符串放进去
         path.push_back(temp);
         dfs(x+i,s);
         path.pop_back();
     }
 }
    vector restoreIpAddresses(string s) {
        if(s.size()>4*3)return ans;//数据范围3000吓唬谁呢 255 255 255 255
        dfs(0,s);//下标
        return ans;
    }
};