93. Restore IP Addresses

problem description

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

algorithm thought

其实是一道典型的回溯法问题。首先第一个位置放一个字符，然后进如下一个函数，运行完回溯之后，放两个字符。然后是3个。中间判断非法情况，如果长度大于1并且第一个字符是'0',显然不行。如果转化为数字之后，数值大于255，显然也是不行的。如果所有情况都满足，最后将结果push到res中。

上面介绍的是回溯的情况，其实可以不需要回溯。因为肯定有4个地方需要我们放置数字，我们只需要3个循环，每个循环处理1-3个字符的情况。

code

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        for(int a=1;a<=3;++a){
            for(int b=1;b<=3;++b){
                for(int c=1;c<=3;++c){
                    for(int d=1;d<=3;++d){
                        if(a+b+c+d!=s.size())
                            continue;
                        string s1=s.substr(0,a);
                        string s2=s.substr(a,b);
                        string s3=s.substr(a+b,c);
                        string s4=s.substr(a+b+c,d);
                        
                        if((s1[0]=='0'&&s1.size()!=1)||(s2[0]=='0'&&s2.size()!=1)||(s3[0]=='0'&&s3.size()!=1)||(s4[0]=='0'&&s4.size()!=1))
                            continue;
                        //cout<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<'-';
                        //cout<<atoi(s1.c_str())<<(atoi(s1.c_str())<=255)<<' ';
                        if((atoi(s1.c_str())<=255)&&(atoi(s2.c_str())<=255)&&(atoi(s3.c_str())<=255)&&(atoi(s4.c_str())<=255))
                        res.push_back(s1+'.'+s2+'.'+s3+'.'+s4);
                    }    
                } 
            }
        }
        return res;
    }
};

algorithm analysis

虽然有4个循环，但是时间复杂度不会很大，因为每个循环就进行3次，循环中的操作时间复杂度可以近似看做O(1)。