做网站卖机械,包装设计公司报价,昊客网络,网站建设职能1. 题目
给定一个只包含数字的字符串#xff0c;复原它并返回所有可能的 IP 地址格式。
示例:
输入: 25525511135
输出: [255.255.11.135, 255.255.111.35]来源#xff1a;力扣#xff08;LeetCode#xff09; 链接#xff1a;http…1. 题目
给定一个只包含数字的字符串复原它并返回所有可能的 IP 地址格式。
示例:
输入: 25525511135
输出: [255.255.11.135, 255.255.111.35]来源力扣LeetCode 链接https://leetcode-cn.com/problems/restore-ip-addresses 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 回溯算法
相关题目LeetCode 468. 验证IP地址
class Solution {vectorstring ans;
public:vectorstring restoreIpAddresses(string s) {if(s.size() 4 || s.size() 12)return {};bt(s,1,0);//从第一个字符前面开始插入.return ans;}void bt(string s, int idx, int count){if(count 3)//3个.才行return;if(count 3 isIPv4(s)){ans.push_back(s);return;}for(int i idx; i s.size(); i){s.insert(i,.);bt(s,i2,count1);//插入后至少向后移动2个位置再插入新的.s.erase(i,1);//回溯删除1个字符 . }}bool isIPv4(string IP) //参考leetcode 468{vectorstring part;split(IP, part);int s, i;for(auto p : part){s 0;if(p || (p[0] 0 p.size() ! 1)) //不能有前置0return false;for(i 0; i p.size(); i){if(!isdigit(p[i]))return false;s s*10p[i]-0;if(s 255) //数字不能超范围return false;}}return true;}void split(string IP, vectorstring part){string p;for(int i 0; i IP.size(); i){if((IP[i]. || i IP.size()-1)){if(i IP.size()-1)p IP[i];part.push_back(p);p ;}elsep IP[i];}}
};
