现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
例如：
给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)
数据范围：字符串长度 
要求：空间复杂度 )
,时间复杂度
注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。
[编程题]数字字符串转化成IP地址
import java.util.ArrayList;
public class Solution {
/*
* 三个循环，注意每个循环的终止条件
*/
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> ans = new ArrayList<String>();
int len = s.length();
for (int i = 1; i < 4 && i < len - 2; i++)
for (int j = i + 1; j < i + 4 && j < len - 1; j++) {
for (int k = j + 1; k < j + 4 && k < len; k++) {
if (len - k >= 4)
continue;
int a, b, c, d;
a = Integer.parseInt(s.substring(0, i));
b = Integer.parseInt(s.substring(i, j)); // that later.
c = Integer.parseInt(s.substring(j, k));
d = Integer.parseInt(s.substring(k));
if (a > 255 || b > 255 || c > 255 || d > 255)
continue;
String ip = a + "." + b + "." + c + "." + d;
if (ip.length() < len + 3)
continue;
ans.add(ip);
}
}
return ans;
}
}
发表于 2017-07-24 15:57:14
回复(3)
AC:
class Solution {
private:
vector<string> result;
public:
vector<string> restoreIpAddresses(string s) {
string res;
dfs(s, res, 0, 0);
return result;
}
void dfs(string s, string& res, int depth, int cnt){
if(depth == s.length() && cnt == 4){
result.push_back(res.substr(0, res.length()-1));
return;
}
if(cnt > 4)
return;
for(int i = 1; i <= 3; i++){
if(depth + i > s.length())
return;
string str = s.substr(depth, i);
int tmp = atoi(str);
if(IsLegal(tmp)){
res = res + str + '.';
dfs(s, res, depth+i, cnt+1);
str = res.substr(0, res.length()-i-1);
res = str;
}
}
}
bool IsLegal(int num){
if(num <= 255 && num >= 0){
return true;
}
return false;
}
int atoi(string s){
int len = s.length();
int result = 0;
if(len > 1 && s[0] == '0') return -1;
for(int i = 0; i < len; i++){
result = result * 10 + int(s[i] - '0');
}
return result;
}
};
编辑于 2016-04-29 20:04:01
回复(1)
枚举所有分割点可能出现的位置，在根据分割点间数字的约束条件进行筛选，将合适的结果加入res
class Solution:
def restoreIpAddresses(self , s: str) -> List[str]:
res = []
i = 1
n = len(s)
while i < 4 and i < n - 2:
j = i + 1
while j < i + 4 and j < n - 1:
k = j + 1
while k < j + 4 and k < n:
if n - k >= 4:
k += 1
continue
a = s[:i]
b = s[i:j]
c = s[j:k]
d = s[k:]
if int(a) > 255 or int(b) > 255 or int(c) > 255 or int(d) > 255:
k += 1
continue
if (len(a) > 1 and a[0] == '0') or (len(b) > 1 and b[0] == '0') or (len(c) > 1 and c[0] == '0') or (len(d) > 1 and d[0] == '0'):
k += 1
continue
temp = a + '.' + b + '.' + c + '.' + d
res.append(temp)
k += 1
j += 1
i += 1
return res
发表于 2022-05-23 17:36:59
回复(0)
class Solution {
private:
vector<string> res;
void backtracking(string &s,int startindex,int pointnum){
if(pointnum==3){
if(isvail(s,startindex,s.size()-1)){
res.push_back(s);
}
return ;
}
for(int i=startindex;i<s.size();i++){
if(isvail(s,startindex,i)){
s.insert(s.begin()+i+1,'.');
pointnum++;
backtracking(s, i+2, pointnum);
pointnum--;
s.erase(s.begin()+i+1);
}else{
break;
}
}
}
bool isvail(const string &s,int start,int end){
if(start>end)return false;
if(s[start]=='0'&&start!=end){
return false;
}
int num=0;
for(int i=start;i<=end;i++){
if(s[i]>'9'||s[i]<'0')return false;
num =num*10+(s[i]-'0');
if(num>255)return false;
}
return true;
}
public:
/**
*
* @param s string字符串
* @return string字符串vector
*/
vector<string> restoreIpAddresses(string s) {
// write code here
res.clear();
if(s.size()>12)return res;
backtracking(s,0,0);
return res;
}
};
发表于 2022-03-17 16:42:52
回复(0)
java屎山
import java.util.*;
public class Solution {
/**
*
* @param s string字符串
* @return string字符串ArrayList
*/
ArrayList<String> res = new ArrayList<String>() ;
public ArrayList<String> restoreIpAddresses (String s) {
// write code here
StringBuilder sb = new StringBuilder("");
back(s,sb,0,0) ;
return res ;
}
public void back(String s , StringBuilder sub, int flag , int count){
if(count >= 4){
if(flag >= s.length()){
res.add(sub.toString().substring(1,sub.toString().length())) ;
System.out.print(sub.toString());
return ;
}
else return ;
}
else{
int i = 1 ;
while(i<4){
if(flag+i<=s.length()){
String value = s.substring(flag,flag+i);
if(Integer.parseInt(value)>=0
&&Integer.parseInt(value)<=255
&&String.valueOf(Integer.parseInt(value)).equals(value)){
sub.append(".");
sub.append(value);
back(s,sub,flag+i,count+1);
sub.delete(sub.length()-i-1,sub.length()) ;
}
}
i++;
}
}
}
}
发表于 2022-02-16 17:12:16
回复(0)
class Solution {
public:
/**
*
* @param s string字符串
* @return string字符串vector
*/
vector<string> restoreIpAddresses(string s) {
int n = s.size();
vector<string> res;
if(n<4) return res;
for(int i=0;i<n-3;++i){
for(int j=i+1;j<min(n-2,i+4);++j){
for(int k=j+1;k<min(n-1,j+4);++k){
string s1 = s.substr(0,i+1);
string s2 = s.substr(i+1,j-i);
string s3 = s.substr(j+1,k-j);
string s4 = s.substr(k+1,n-1-k);
if(isIpAdd(s1) && isIpAdd(s2) && isIpAdd(s3) && isIpAdd(s4))
res.push_back(s1+"."+s2+"."+s3+"."+s4);
}
}
}
return res;
}
bool isIpAdd(string s){
if(s.empty()) return false;
if(s.size()>1 && s[0]=='0') return false;
if(stoi(s)>=0 && stoi(s)<=255) return true;
return false;
}
};
发表于 2021-12-20 00:56:53
回复(0)
import java.util.*;
public class Solution { //很巧妙的dfs，调了一早上
ArrayList<String> res = new ArrayList<>();
ArrayList<String> track = new ArrayList<>();
public ArrayList<String> restoreIpAddresses (String s) {
if(s.length() < 4) return new ArrayList<>();
dfs(s,0);
return res;
}
public void dfs(String s,int start){
int len = s.length();
if(track.size() == 4 && start != len)//不合法
return;
if(track.size() == 4 && start == len){
res.add(track.get(0) + "." + track.get(1) + "."
+ track.get(2) + "."+track.get(3));
}
for(int i = start,j = i + 1;j < len + 1 && j - i <= 3;j++){
if(validate(s.substring(i,j))) { //数字合法
track.add(s.substring(i,j));
dfs(s,j); //向下搜
track.remove(track.size() - 1);
}
}
}
private boolean validate(String s) {
if(s.equals("0")) return true;
if(s.startsWith("0")) return false;
return Integer.parseInt(s) <= 255;
}
}
发表于 2021-10-25 10:39:52
回复(0)
template <typename T>
std::string join(T& val, char delim) {
std::ostringstream str;
const typename T::iterator itlast = val.end() - 1;
for (auto it = val.begin(); it != val.end(); ++it) {
str << *it;
if (it != itlast) str << delim;
}
return str.str();
}
class Solution {
public:
/**
* key: ip地址不能有 leading zeroes 前导零
* @param s string字符串
* @return string字符串vector
*/
vector<string> restoreIpAddresses(string s) {
const int n = s.length();
vector<string> ans;
vector<int> candidates;
function<void(int)> backtracking = [&](int p) {
if (candidates.size() == 4) {
if (p == n) ans.emplace_back(join(candidates, '.'));
return;
}
int num = 0;
for (int i = p; i < n; ++i) {
num = num * 10 + s[i] - 48;
if (num > 255) return; // pruning
candidates.emplace_back(num);
backtracking(i + 1);
candidates.pop_back(); // backtracking
if (s[p] == 48) return; // 如果遇到前导零就无需向后扩展了
}
};
backtracking(0);
return ans;
}
};
发表于 2021-07-07 10:50:38
回复(0)
import java.util.*;
public class Solution {
private String s; //传入的数字字符串
private ArrayList<String> result = new ArrayList<>(); // 存放结果
public ArrayList<String> restoreIpAddresses (String s) {
if (s == null || s.length() < 4){
return new ArrayList<String>();
}
this.s = s;
int remain= s.length(); // 剩余需要处理的长度
int index = 0; // 当前处理的下标
int chance = 4; // 剩余的打点机会
StringBuilder sb = new StringBuilder();
process(remain, chance, index, sb);
return result;
}
private void process(int remain, int chance, int index, StringBuilder sb){
if (remain == 0){
if (chance == 0){ // 处理完所有字符串且刚刚用完机会
result.add(sb.substring(0, sb.length()-1));
}
return;
}
if (chance == 0){ //没处理完字符串且没机会了
return;
}
// 假设拿1位出来
process(remain-1, chance-1, index+1, new StringBuilder(sb).append(s.substring(index, index+1)).append('.'));
// 假设拿2位出来
if (remain >= 2 && s.charAt(index) != '0'){
process(remain-2, chance-1, index+2,new StringBuilder(sb).append(s.substring(index, index+2)).append('.'));
}
// 假设拿3位出来
if (remain >= 3 && s.charAt(index) != '0'){
if (Integer.parseInt(s.substring(index, index+3)) <= 255){
process(remain-3, chance-1, index+3,new StringBuilder(sb).append(s.substring(index, index+3)).append('.'));
}
}
return;
}
}
发表于 2021-07-06 18:09:46
回复(0)
public class Solution {
/**
*
* @param s string字符串
* @return string字符串ArrayList
*/
public ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> restoreIpAddresses (String s) {
if(s.length() < 4) return res;
ArrayList<String> tmp = new ArrayList<String>();
String now = "";
dfs(s, 0, tmp, now);
return res;
}
public void dfs(String str, int k, ArrayList<String> stmp, String now){
if(stmp.size() > 3) return;
if(k == str.length()-1){
now = now + str.charAt(k);
if(now.length() <= 3 && Integer.parseInt(now) <= 255 && stmp.size() == 3){
String result = stmp.get(0) + "." + stmp.get(1) + "." + stmp.get(2) + "." + now;
res.add(result);
}
return;
}
if(Integer.parseInt(now + str.charAt(k)) <= 255){
// 位置1
stmp.add(now + str.charAt(k));
dfs(str, k+1, stmp, "");
stmp.remove(stmp.size()-1);
// 位置2
if(!(now.equals("") && str.charAt(k) == '0')){
dfs(str, k+1, stmp, now + str.charAt(k));
} // 代码换个位置你就给我报错？？？？这段代码在位置1你就不给通过？？？ 说好的顺序无关的呢
}
// stmp.add(now);
// dfs(str, k+1, stmp, str.charAt(k)+"");
// stmp.remove(stmp.size()-1);
}
}
/**
*
* @param s string字符串
* @return string字符串ArrayList
*/
public ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> restoreIpAddresses (String s) {
if(s.length() < 4) return res;
ArrayList<String> tmp = new ArrayList<String>();
String now = "";
dfs(s, 0, tmp, now);
return res;
}
public void dfs(String str, int k, ArrayList<String> stmp, String now){
if(stmp.size() > 3) return;
if(k == str.length()-1){
now = now + str.charAt(k);
if(now.length() <= 3 && Integer.parseInt(now) <= 255 && stmp.size() == 3){
String result = stmp.get(0) + "." + stmp.get(1) + "." + stmp.get(2) + "." + now;
res.add(result);
}
return;
}
if(Integer.parseInt(now + str.charAt(k)) <= 255){
// 位置1
stmp.add(now + str.charAt(k));
dfs(str, k+1, stmp, "");
stmp.remove(stmp.size()-1);
// 位置2
if(!(now.equals("") && str.charAt(k) == '0')){
dfs(str, k+1, stmp, now + str.charAt(k));
} // 代码换个位置你就给我报错？？？？这段代码在位置1你就不给通过？？？ 说好的顺序无关的呢
}
// stmp.add(now);
// dfs(str, k+1, stmp, str.charAt(k)+"");
// stmp.remove(stmp.size()-1);
}
}
发表于 2021-07-03 17:19:24
回复(0)
找到所有情况一看就是回溯去做
剪枝的话就是提前判断剩余长度是不是合理长度，比如剩3个段，那么长度就应该是 3 <= len <= 9
class Solution {
public:
vector<string> ans;
vector<string> restoreIpAddresses(string s) {
backTrace(s, 0, {}, 0);
return ans;
}
void backTrace(string &s, int idx, vector<string> pre, int depth) {
if (s.size() - idx > (4 - depth) * 3) return;
if (s.size() - idx < (4 - depth)) return;
if (depth == 3) {
if (isValid(s.substr(idx))) {
string res;
for (auto ipf : pre) {
res += ipf + ".";
}
res += s.substr(idx);
ans.push_back(res);
}
return;
}
for (int len = 1; len < 4; len++) {
string tmps = s.substr(idx, len);
if (isValid(tmps)) {
pre.push_back(tmps);
backTrace(s, idx+len, pre, depth+1);
pre.pop_back();
}
}
}
bool isValid(string s) {
int tmpi = std::stoi(s);
if (s.size() > 1 && s[0] == '0') return false;
return tmpi >= 0 && tmpi <= 255;
}
};
发表于 2020-09-17 10:53:01
回复(0)
/*
* 目的：所有可能的IP地址
* 方法：穷举
* 注意：每一部分的开头不能是'0',并且不能大于"255"
*/
void solve(string s, string cur, int num, vector<string>&res){
if (num==4){
if (s== ""){
cur=cur.substr(0, cur.size()-1);
res.push_back(cur);
}
return;
}
if (num<4 && s=="")
return;
string temp="";
for (int i = 1;i<=min(3,int(s.size())); ++i){
temp = s.substr(0,i);
if ((temp[0] == '0' && i>1)|| stoi(temp)>255)
continue;
solve(s.substr(i,s.size()-i),cur+temp+".", num+1,res);
}
}
vector<string> restoreIpAddresses(string s) {
vector<string>res;
solve(s,"",0, res);
return res;
}
发表于 2019-12-08 16:37:11
回复(0)
class Solution {
public:
int sitoi(string s)
{
int sum=0;
for(int i=0;i<s.size();++i)
sum=sum*10+s[i]-'0';
return sum;
}
void IpAddress(string str,int cnt,string obj,vector<string>&ans)
{
if(str.size()<=0) return ;
if(cnt==4)
{
if(str.size()<=3&&sitoi(str)<=255)
{
if(str.size()==1||str.size()!=1&&str[0]!='0')
{
obj+=str;
ans.push_back(obj);
}
}
return ;
}
if(str.size()>3)
{
IpAddress(str.substr(1,str.size()),cnt+1,obj+str.substr(0,1)+'.',ans);
if(str[0]!='0') IpAddress(str.substr(2,str.size()),cnt+1,
obj+str.substr(0,2)+'.',ans);
if(str[0]-'2'<=0&&str[0]!='0'&&sitoi(str.substr(0,3))<=255)
IpAddress(str.substr(3,str.size()),cnt+1,obj+str.substr(0,3)+'.',ans);
}
else if(str.size()>2)
{
IpAddress(str.substr(1,str.size()),cnt+1,obj+str.substr(0,1)+'.',ans);
if(str[0]!='0') IpAddress(str.substr(2,str.size()),cnt+1,
obj+str.substr(0,2)+'.',ans);
}
else if(str.size()>1)
IpAddress(str.substr(1,str.size()),cnt+1,obj+str.substr(0,1)+'.',ans);
}
vector<string> restoreIpAddresses(string s) {
vector<string>res;
string temp="";
IpAddress(s,1,temp,res);
return res;
}
};
发表于 2019-06-03 18:47:54
回复(0)
vector<string> restoreIpAddresses(string s) {
vector<string> ret;
if (s.empty()) { return ret; }
// tmp_ip存储截出的各个IP段
vector<string> tmp_ip;
for (int i = 1; i <= (s.size() < 3 ? s.size() : 3); i++) { // 每次依次截取1、2、3位
string tmp = s.substr(0, i);
if (isLegalIp(tmp)) {
tmp_ip.push_back(tmp);
restoreIpCore(s.substr(i), tmp_ip, ret); // 递归处理去掉截除前几位的后续字符串
tmp_ip.pop_back();
}
}
return ret;
vector<string> ret;
if (s.empty()) { return ret; }
// tmp_ip存储截出的各个IP段
vector<string> tmp_ip;
for (int i = 1; i <= (s.size() < 3 ? s.size() : 3); i++) { // 每次依次截取1、2、3位
string tmp = s.substr(0, i);
if (isLegalIp(tmp)) {
tmp_ip.push_back(tmp);
restoreIpCore(s.substr(i), tmp_ip, ret); // 递归处理去掉截除前几位的后续字符串
tmp_ip.pop_back();
}
}
return ret;
}
void restoreIpCore(string s, vector<string> &tmp_ip, vector<string> &ret) {
if (s.empty()) {
if (tmp_ip.size() != 4) { return; } // 有效IP地址只有4个IP段
string ip;
for (int i = 0; i < tmp_ip.size(); i++) { // 拼出IP地址
ip.append(tmp_ip[i]);
if (i < tmp_ip.size() - 1) {
ip.append(".");
}
}
ret.push_back(ip);
return ;
}
for (int i = 1; i <= (s.size() < 3 ? s.size() : 3); i++) {
string tmp = s.substr(0, i);
if (isLegalIp(tmp)) {
tmp_ip.push_back(tmp);
restoreIpCore(s.substr(i), tmp_ip, ret);
tmp_ip.pop_back();
}
}
}
if (s.empty()) {
if (tmp_ip.size() != 4) { return; } // 有效IP地址只有4个IP段
string ip;
for (int i = 0; i < tmp_ip.size(); i++) { // 拼出IP地址
ip.append(tmp_ip[i]);
if (i < tmp_ip.size() - 1) {
ip.append(".");
}
}
ret.push_back(ip);
return ;
}
for (int i = 1; i <= (s.size() < 3 ? s.size() : 3); i++) {
string tmp = s.substr(0, i);
if (isLegalIp(tmp)) {
tmp_ip.push_back(tmp);
restoreIpCore(s.substr(i), tmp_ip, ret);
tmp_ip.pop_back();
}
}
}
bool isLegalIp(string &str) {
// "01" 或 "010"均是非法ip段，只有"0"才是合法ip段
if (str.size() > 1 && str[0] == '0') { return false; }
// 合法ip段 <= 255
if (atoi(str.c_str()) > 255) { return false; }
return true;
}
// "01" 或 "010"均是非法ip段，只有"0"才是合法ip段
if (str.size() > 1 && str[0] == '0') { return false; }
// 合法ip段 <= 255
if (atoi(str.c_str()) > 255) { return false; }
return true;
}
发表于 2019-02-05 11:40:55
回复(0)
//参考三楼答案，主要思路是递归分割字符串，判断切割的字符串是否合法（能转换成0-255的整数）
//同时记录分割的段数（IPv4地址都是4段划分），如果达到4段且每段字符串均合法，则加入到结果中
class Solution {
public:
void dfs(vector<string> &v,string lstr,string rstr,int ind)
{
if(ind==3 && isValid(rstr))
{
v.push_back(lstr + rstr);
return;
}
string sub;
//i代表本次字符串切割长度，从首位字符开始，i<4是因为转换成数字应不大于255（三位）
for(int i=1;i<4&&i<rstr.size();i++)
{
sub = rstr.substr(0,i);
if(isValid(sub))
{
sub = lstr + sub + '.';
dfs(v,sub,rstr.substr(i),ind+1);
}
}
}
vector<string> restoreIpAddresses(string s) {
vector<string> v;
dfs(v,"",s,0);
return v;
}
bool isValid(string &s)
{
stringstream ss(s);
int num;
ss >> num;
if(s.size()>1)
{
return s[0]!='0' && num>=0 && num<=255;
}
return num>=0 && num<=255;
}
};
编辑于 2019-01-02 15:18:27
回复(0)
class Solution {
vector<string> res;
string d="",s;
public:
vector<string> restoreIpAddresses(string s) {
this->s=s,dfs(0,0);
return res;
}
void dfs(int step,int index){
string cur="";
if(step==4){
if(index!=s.length()) return;
res.push_back(d);
}else
for(int i=index;i<index+3&&i<s.length();i++){
cur+=s[i];
int tmp=atoi(cur.c_str());
string temp=d;
if(tmp>=0&&tmp<=255&&(cur.length()==1||cur[0]!='0')){
step-3?d+=cur+".":d+=cur;
dfs(step+1,i+1),d=temp;
}
}
}
};
发表于 2017-10-24 19:20:02
回复(0)
import java.util.*;
public class Solution {
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
StringBuffer sb = new StringBuffer();
dfs(res, sb, 4, 0, s);
return res;
}
public void dfs(ArrayList<String> res, StringBuffer sb, int nums, int start, String s) {
if(nums == 1){
String ipstr = s.substring(start);
if(ipstr.matches("[0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5]")){
sb.append(ipstr);
res.add(sb.toString());
sb.delete(sb.length() - ipstr.length(), sb.length());
}
}
else {
for(int i=start+1; i<=s.length() - nums + 1; i++) {
int leftLen = s.length() - i;
if(leftLen <= 3 * (nums-1) && leftLen >= (nums-1)) {
String ipstr = s.substring(start, i);
if(ipstr.matches("[0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5]")){
sb.append(ipstr+ ".");
dfs(res, sb, nums-1, i, s);
sb.delete(sb.length() - ipstr.length() - 1, sb.length());
}
}
}
}
}
}
发表于 2017-06-25 15:38:20
回复(0)
public static ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> res = new ArrayList<String>(); if (s.length() > 12) { return res; } _restoreIpAddress(s, 0, "", res); ArrayList<String> result=new ArrayList<String>(); for (String s1 : res) { int len = s1.split("\\.").length; if (len == 4) { result.add(s1); } } return result; } private static void _restoreIpAddress(String s, int start, String item, ArrayList<String> res) { if (start >= s.length()) { res.add(item); return; } for (int i = start; i < s.length(); i++) { String str = s.substring(start, i + 1); if (isLegal(str)) { String newStr; if (item.length() > 0) { newStr = item + "." + str; } else { newStr = str; } _restoreIpAddress(s, i + 1, newStr, res); } } } private static boolean isLegal(String str) { if (str.length() > 3) { return false; } if(str.length()==3&&str.charAt(0)=='0'){ return false; } if(str.length()==2&&str.charAt(0)=='0'){ return false; } Integer num = Integer.parseInt(str); if (num <= 255 && num >= 0) { return true; } return false; }
编辑于 2016-09-08 15:34:40
回复(0)
//深搜
import java.util.ArrayList;
public class Solution {
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<>();
ArrayList<String> ip = new ArrayList<>(); //存放中间结果
dfs(s, res, ip, 0);
return res;
}
private void dfs(String s, ArrayList<String> res, ArrayList<String> ip, int start){
if(ip.size() == 4 && start == s.length()){ //找到一个合法解
res.add(ip.get(0) + '.' + ip.get(1) + '.' + ip.get(2) + '.' + ip.get(3));
return;
}
if(s.length() - start > 3 * (4 - ip.size())) //剪枝
return;
if(s.length() - start < (4 - ip.size())) //剪枝
return;
int num = 0;
for(int i = start; i < start + 3 && i < s.length(); i++){
num = num * 10 + (s.charAt(i) - '0');
if(num < 0 || num > 255) //剪枝
continue;
ip.add(s.substring(start, i + 1));
dfs(s, res, ip, i + 1);
ip.remove(ip.size() - 1);
if(num == 0) //不允许前缀0
break;
}
}
}
编辑于 2017-08-03 20:08:51
回复(3)
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> result;
string t;
DFS(result,t,s,0);
return result;
}
void DFS(vector<string> &result, string t, string s, int count)
{
if(count==3 && isValid(s))
{
result.push_back(t+s);
return;
}
for(int i=1;i<4 && i<s.size();i++)
{
string sub = s.substr(0,i);
if(isValid(sub))
DFS(result, t+sub+'.', s.substr(i),count+1);
}
}
bool isValid(string &s)
{
stringstream ss(s);
int num;
ss>>num;
if(s.size()>1)
return s[0]!='0' && num>=0 && num<=255;
return num>=0 && num<=255;
}
};
发表于 2017-09-08 01:38:55
回复(4)
问题信息
难度：
182条回答
1063收藏
37428浏览
通过挑战的用户
查看代码-
2023-03-06 23:10:27
-
2023-02-21 11:19:43
-
2022-12-02 14:38:04 -
2022-10-26 23:08:36
-
2022-10-26 17:08:16
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
