专栏首页Michael阿明学习之路LeetCode 93. 复原IP地址(回溯)

LeetCode 93. 复原IP地址(回溯)

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 {
	vector<string> ans;
public:
    vector<string> 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,i+2,count+1);//插入后,至少向后移动2个位置再插入新的.
    		s.erase(i,1);//回溯,删除1个字符 . 
    	}
    }

    bool isIPv4(string &IP)	//参考leetcode 468
    {
    	vector<string> part;
    	split(IP, part);
    	int s, i;
    	for(auto p : part)
    	{
    		s = 0;
    		if(p == "" || (p[0] == '0' && p.size() != 1))	//不能有前置0
    			return false;
    		for(i = 0; i < p.size(); ++i)
    		{
    			if(!isdigit(p[i]))
    				return false;
    			s = s*10+p[i]-'0';
    			if(s > 255)	//数字不能超范围
    			    return false;
    		}
    	}
    	return true;
    }

    void split(string &IP, vector<string> &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 = "";
    		}
    		else
    			p += IP[i];
    	}
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 796. 旋转字符串

    A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = ‘abcde’,在移动一次之后结果就是’bcdea’ 。如果在若干次旋转操作之后,A ...

    Michael阿明
  • LeetCode 468. 验证IP地址

    IPv4 地址由十进制数和点来表示,每个地址包含4个十进制数,其范围为 0 - 255, 用(".")分割。比如,172.16.254.1;

    Michael阿明
  • 程序员面试金典 - 面试题 17.07. 婴儿名字(并查集)

    每年,政府都会公布一万个最常见的婴儿名字和它们出现的频率,也就是同名婴儿的数量。 有些名字有多种拼法,例如,John 和 Jon 本质上是相同的名字,但被当成...

    Michael阿明
  • 干货 | 基于红黑树的高效IP归属地查询方案

    作者简介 邢钦华,携程风控团队高级研发经理。2016年加入携程,是风控大数据平台Chloro的设计和开发的主要参与者。专注于大数据流式处理和用户行为分析在互联网...

    携程技术
  • 使用性能优化工具 MVC Mini Profiler (MVC3+EF4.1)

    3,因为我这里使用的是Entity framework 4.1 code first 所以还需要下载 一个包PM> Install-Package MiniPr...

    Isaac Zhang
  • Markdown 编写规范

    文档中使用的关键字「MUST」,「MUST NOT」,「REQUIRED」,「SHALL」,「SHALL NOT」,「SHOULD」,「SHOULD NOT」,...

    java攻城狮
  • 针对基础网络该如何做好DDOS防御?

    今天向一个企业老总学习请教的过程中,聊到了现下关于DDOS攻防的问题。老总说找攻击的高于找防御的。为什么呢?因为大家都知道防御的成本比较高,攻击成本小,而且一部...

    墨者安全科技
  • 01.loc & iloc & ix 区别使用标签选取数据

    当用行号索引的时候, 尽量用 iloc 来进行索引; 而用标签索引的时候用 loc , ix 尽量别用。

    用户1250179
  • C# 正则进阶

    从 .NET Framework 4.5 开始,正则表达式支持在匹配操作中指定超时时间。如果匹配超时,就会抛出 RegexMatchTimeoutExcepti...

    丹枫无迹
  • leetCode刷题(将字符串转成W形状的字符串再以Z形字符串输出)

    windseek

扫码关注云+社区

领取腾讯云代金券