93. 复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"[email protected]"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]示例 2：
输入：s = "0000"
输出：["0.0.0.0"]示例 3：
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]提示：
1 <= s.length <= 20s仅由数字组成
题解
一个字符串会被分割为四部分，每部分长度1到3，并且除部分1外，都不可以有先导0，并且不可以超过255。
根据之前的题目的惯性思路，每次递归传入下标idx，表示此次选择的起点，在循环中，i从1到3，表示此部分选择的长度1到3，将题目要求分别转换为剪枝条件：
- 分割为四部分：
cur.size()==4||idx==s.size()； - 不能超限：
idx+i>s.size()； - 先导
0：i>1&&s[idx]=='0'； - 不可以超过255：
stoi(num) > 255（stoi将string转为int）
查看代码
class Solution {
public:
vector<string> res;
void work(const string& s,int idx,vector<string>& cur){
//分割得到4部分并且遍历完了
if(cur.size()==4&&idx==s.size()){
res.emplace_back(cur[0]+"."+cur[1]+"."+cur[2]+"."+cur[3]);
return;
}
//已经有四部分了|已经遍历完了
if(cur.size()==4||idx==s.size())
return;
//每部分只有1到3个数字
for(int i=1;i<=3;i++){
//超限
if(idx+i>s.size())
return;
//"0.1.2.201"有效而"0.011.255.245"无效
if(i>1&&s[idx]=='0')
return;
//选取idx到i的为一个部分
const string& num = s.substr(idx, i);
//stoi参数为const string&
if(stoi(num) > 255)
return;
cur.emplace_back(num);
work(s,idx+i,cur);
cur.pop_back();
}
}
vector<string> restoreIpAddresses(const string& s) {
vector<string> cur;
work(s,0,cur);
return res;
}
};标签：return,cur,idx,IP,力扣,地址,93,size From： https://www.cnblogs.com/fudanxi/p/17262560.html