刷题主页
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。 示例: 输入: “25525511135” 输出: [“255.255.11.135”, “255.255.111.35”]
该题是列出所有可能的ip地址格式，属于在一个范围内找到所有符合条件类的题，因此直接使用回溯法即可，重点在于剪枝部分。
class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string>res; if(s.size()==0)return res; vector<string>cur; backtrack(s,0,cur,res); return res; } void backtrack(string s,int index,vector<string>&cur,vector<string>&res){ if(cur.size()==4){ if(index==s.size()){ string str=cur[0]+"."+cur[1]+"."+cur[2]+"."+cur[3]; res.push_back(str); } return; } for(int i=1;i<=3;++i){ if(index+i>s.size())break; string temp=s.substr(index,i); if((temp[0]=='0' && temp.size()>1) || stoi(temp)>255)continue; cur.push_back(temp); backtrack(s,index+i,cur,res); cur.pop_back(); } } };