93.复原IP地址
原题链接：93. 复原 IP 地址 - 力扣（LeetCode）
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
思路详解；本题我们用dfs来搜索每一次能分割成的字符，然后拼接起来即可
（1）声明两个数组，一个用来存储结果，一个用来存储当前分割的字符串
（2）我们将字符串分成四个数字，如果达到第四个数字且字符数组遍历结束没有跳出循环，我们认为当前字符符合IP地址的要求，将他加入结果集
（3）分割时我们需要先将字符转化为int类型，然后当分割后的数字>255，或前导为0直接跳出循环即可
代码详解；
class Solution {vector<string>ans;//结果数组vector<int>cur;//存储当前已经分好的数组
public:vector<string> restoreIpAddresses(string s) {dfs(s,0,0);return ans;}void dfs(string& s,int index,int start)//参数包括，字符串，当前分割字符串数，当前字符串起始下标{if(index==4&&start==s.length())//如果分割到第四个数字且下表已经移动到尾，说明是有效IP{string ip=to_string(cur[0]);//将第一组ip转换成字符for(int i=1;i<cur.size();i++)//遍历{ip=ip+'.'+to_string(cur[i]);//用.连接并转化为字符}ans.push_back(ip);//加入结果集return;}for(int i=start,num=0;i<s.length();i++)//从start开始分割，num代表当前数字{num=num*10+s[i]-'0';//将当前字符拼接起来转成整数if(num>255)break;//大于255跳出cur.push_back(num);//否则加入dfs(s,index+1,i+1);//下一个位置继续搜索cur.pop_back();if(num==0)break;//有前导0也结束循环}}
};