LeetCode-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)

class Solution {
public:
    void sub(string &s,string&ret,int start,int level,vector<string>& vec){
        if(level==3){
            if(start<s.length()&&s.length()-start<=3){
                if(s.length()-start>1&&s[start]=='0')return;
                int val=0;
                for(int i=start;i<s.length();i++){
                    val*=10;
                    val+=s[i]-'0';
                }
                if(val>=0&&val<=255){
                    int size=ret.length();
                    ret+='.';
                    for(int i=start;i<s.length();i++){
                        ret+=s[i];
                    } 
                    vec.push_back(ret);
                    ret.resize(size);
                }
            }
        }
        else {
            if(start<s.length()&&s.length()-start>=4-level){
                int val=0;
                int i=0;
                for(;i<3;i++){
                    if(i>=1&&s[start]=='0')return;
                    if(s.length()-start-i<4-level){
                        return;
                    }
                    else{
                        val*=10;
                        val+=s[start+i]-'0';
                        if(val>=0&&val<=255){
                            
                            int size=ret.length();
                            if(level!=0)ret+='.';
                            for(int j=0;j<=i;j++){
                                ret+=s[start+j];
                            }
                            sub(s,ret,start+i+1,level+1,vec);
                            ret.resize(size);
                        }
                        else{
                            return;
                        }
                    }
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<string> ret;
        string one="";
        sub(s,one,0,0,ret);
        return ret;
    }
};
View Code
原文地址:https://www.cnblogs.com/superzrx/p/3351159.html