首页 > 试题广场 >

数字字符串转化成IP地址

[编程题]数字字符串转化成IP地址
  • 热度指数:66624 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
现在有一个只包含数字的字符串,将该字符串转化成IP地址的形式,返回所有可能的情况。
例如:
给出的字符串为"25525522135",
返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围:字符串长度 0 \leq n \leq 12
要求:空间复杂度 ,时间复杂度

注意:ip地址是由四段数字组成的数字序列,格式如 "x.x.x.x",其中 x 的范围应当是 [0,255]。

示例1

输入

"25525522135"

输出

["255.255.22.135","255.255.221.35"]
示例2

输入

"1111"

输出

["1.1.1.1"]
示例3

输入

"000256"

输出

[]
import java.util.ArrayList;

public class Solution {
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> result = new ArrayList<>();

        int length = s.length();
        for (int i = 1; i <= 3; i++) {
            for (int j = 1; j <= 3; j++) {
                for (int m = 1; m <= 3; m++) {
                    for (int n = 1; n <= 3; n++) {
                        if (i + j + m + n == length) {
                            String one = s.substring(0, i);
                            String two = s.substring(i, i+j);
                            String three = s.substring(i+j, i+j+m);
                            String four = s.substring(i+j+m, i+j+m+n);

                            if ((Integer.valueOf(one) >= 0 && Integer.valueOf(one) <= 255) && (Integer.valueOf(two) >= 0 && Integer.valueOf(two) <= 255) && (Integer.valueOf(three) >= 0 && Integer.valueOf(three) <= 255) && (Integer.valueOf(four) >= 0 && Integer.valueOf(four) <= 255)) {
                                if (one.length() == 1 || one.charAt(0) != '0')
                                    if (two.length() == 1 || two.charAt(0) != '0')
                                        if (three.length() == 1 || three.charAt(0) != '0')
                                            if (four.length() == 1 || four.charAt(0) != '0')
                                                result.add(one+"."+two+"."+three+"."+four);
                            }
                        }
                    }
                }
            }
        }

        return result;
    }
}

编辑于 2017-05-24 10:11:40 回复(9)
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);
        
    }
}

发表于 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;
}

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();
        }
    }
}

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;
}

发表于 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)