数字字符串转化成IP地址

枚举所有分割点可能出现的位置，在根据分割点间数字的约束条件进行筛选，将合适的结果加入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

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

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

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

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

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

    /*
    * 目的：所有可能的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;
    }

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

//参考三楼答案，主要思路是递归分割字符串，判断切割的字符串是否合法（能转换成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;
    }
};

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

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

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

//深搜
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;
        }
    }
}

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

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