Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given"25525511135"
,
return["255.255.11.135", "255.255.111.35"]
. (Order
does not matter)
情况多得让人天旋地转的题目,非常繁琐,只能一个条件一个条件地满足了。
本题学了个新的函数:stoi;不过注意这个函数只能是转换int大小的,超过了int的边界就会溢出。跟我们用什么数据类型保存stoi的结果无关。
主要考验递归回溯和剪枝的真功夫了。看来这三个技能都是算法必修的,还要可以很灵活运用,否则这样的题目不可能做出来。
class Solution {
public:
vector<string> restoreIpAddresses(string s)
{
vector<string> vs;
if (s.empty() || s.length()>12) return vs;
restore(s, vs);
return vs;
}
bool isLegalIPSec(string s)
{
//注意:数据太大会领导i溢出,所以别忘记加判断s.length()>3
if (s.empty() || s.length() > 3) return false;
//注意:01,02,033等情况,但是0是合法的
if (s.length()>1 && s[0] == '0') return false;
//因为stoi只能是转换成为int大小,超过INT_MIN INT_MAX就会溢出
int i = stoi(s);
return i>=0 && i<=255;
}
void restore(string &s, vector<string> &vs, string itmedia="", int num=1)
{
if (s.empty()) return;
if (num == 4 && isLegalIPSec(s))
{
itmedia += s;
vs.push_back(itmedia);
return;
}
else if (num == 4) return;
//注意要加s.length()否则会在1111等四个字符中超标的
for (int i = 1; i < 4 && i<s.length(); i++)
{
string t = s.substr(0,i);
if (isLegalIPSec(t))
{
itmedia.append(t + ".");
}
else return;
t = s.substr(i);
restore(t, vs, itmedia, num+1);
//注意别忘了判空的情况
if (!itmedia.empty()) itmedia.pop_back();
while (!itmedia.empty() && itmedia.back() != '.') itmedia.pop_back();
}
}
};
//2014-2-14 update
vector<string> restoreIpAddresses(string s)
{
vector<string> rs;
string tmp;
restore(rs, tmp, s);
return rs;
}
void restore(vector<string> &rs, string &tmp, string &s, int k=1, int begin=0)
{
if (k == 4)
{
string t = s.substr(begin);
if (isLegal(t)) rs.push_back(tmp+"."+t);
return;
}
for (int len = 1; len < 4 && begin+len< s.length(); len++)
{
string t = s.substr(begin, len);
if (!isLegal(t)) return;
if (k != 1) tmp.push_back('.');
tmp.append(s.substr(begin, len));
restore(rs, tmp, s, k+1, begin+len);
while (!tmp.empty() && tmp.back() != '.') tmp.pop_back();
if (!tmp.empty()) tmp.pop_back();
}
}
bool isLegal(string &s)
{
if (s.empty() || s.length() > 3 || s.length() != 1&&s[0]=='0') return false;
int t = stoi(s);
return t < 256;
}
分享到:
相关推荐
leetcode盒子嵌套 leetcode-text 92.Reverse Linked List II Runtime: 4 ms, faster than 67.04% of C online submissions for Reverse Linked List II. Memory Usage: 6.9 MB, less than 100.00% of C online ...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合。对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间。 一个字符串可能可以转化成多个ip地址,我们需要...
python python_leetcode面试题解之第93题复原IP地址_题解
leetcode中文版
restoreIPAddresses 复原IP地址 threeSum 三数之和 search 搜索旋转排序数组 1. 3. 9. 75. 209. 219. 167. 268. 344. 349. 454. 447. 695. 674. string 字符串 20. 150. linklist 链表 19. 24. 86. 92. 203. 206. ...
vs code LeetCode 插件
javascript javascript_leetcode面试题解递归与回溯问题之第93题复原ip地址_题解
100个leetCode详细解答
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 刷题汇总1
LeetCode 选讲1
大佬的leetcode刷题笔记(c++版本)
0093. 复原 IP 地址标签:字符串、回溯难度:中等题目大意给定一个只包含数字的字符串,用来表示一个 IP 地址,返回所有由 s 构成的有效 IP 地址,可
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
leetcode
LeetCode面试笔试题
该分类为结合《算法导论》的内容,给出Leetcode题目分类。题目主要集中在Leetcode的前400题中,也包括有后面的一些经典值得刷的题。该题目分类按照算法和数据结构排版,即可供单独Leetcode刷题使用,也可以配合学习...
leetcode刷题, 直接用leetcode的分类方式.