Restore IP Addresses

In my opinion, this is a backtracing problem, this means you have to iterate all possible valid combination.
Below are my Solutions, hope this will demonstrate clear what the algorithms goes.public ArrayList<String> restoreIpAddresses(String s) { // Start typing your Java solution below // DO NOT write main() function ArrayList<String> result=new ArrayList<String>(); helper(s, 0,"",result); return result; } public void helper(String dataSegment,int level,String temp,ArrayList<String> result){ if(level==4){ if(dataSegment.length()==0) result.add(temp.substring(1)); return; } int possi=dataSegment.length()>=3?3:dataSegment.length(); for(int i=1;i<=possi;i++){ String newOne=dataSegment.substring(0,i); if(isValidSegment(newOne)){ temp+="."+newOne; helper(dataSegment.substring(i), level+1, temp,result); temp=temp.substring(0,temp.lastIndexOf(".")); } } } public boolean isValidSegment(String s){ if(s.charAt(0)=='0') return s.length()==1; Integer result=Integer.parseInt(s); if(result>255) return false; return true; }

Here is a solution from old discuss by soulmachine . Thanks to soulmachine !
I have translated and made a little modification to his post.
General thought of this problem is generate all possible combination of given string by recursion and check if it is a valid ip address, but there are also some optimization in the recursion process.Hope going thru his code with its detailed comment will help you understand the algorithm to this problem.
class Solution { public: vector<string> restoreIpAddresses(string s) { vector<string> result; string ip; // save temporary result in processing dfs(s, 0, 0, ip, result); return result; } /** * @brief: split the string * @param[in] s string，input * @param[in] startIndex, start from which index in s * @param[in] step current step index，start from 0，valid values: 0,1,2,3,4, as special, 4 means ending of split * @param[out] intermediate, split result in current spliting process * @param[out] result, save all possible IP address * @return none */ void dfs(string s, size_t start, size_t step, string ip, vector<string> &result) { if (start == s.size() && step == 4) { // find a possible result ip.resize(ip.size()  1); result.push_back(ip); return; } // since each part of IP address is in 0..255, the length will not more than 3, and not less than 1 as well. if (s.size()  start > (4  step) * 3) return; // optimize, the length of rest part of s string should not more than 3 * remaining part count need to split. if (s.size()  start < (4  step)) return; // optimize, the length of rest part of s string should not less than 1 * remaining part count need to split. int num = 0; for (size_t i = start; i < start + 3; i++) { num = num * 10 + (s[i]  '0'); if (num <= 255) { // current split is valid, go to next recursion. ip += s[i]; dfs(s, i + 1, step + 1, ip + '.', result); } if (num == 0) break; // single 0 is allowed, but '00' is forbidden. } } };

Actually, you can do 3 forloops loops to check all points' position.
Following is more detail. You can get points' positions by i, j, k. Using these positions, you can divide s into candidate ipform. Then, you can judge whether the candidate fits ip.
To improve the efficiency, you can narrow the scope of i, j, k.for (int i = 1; i <= s.len  3; i ++) { for (int j = i + 1; j <= s.len  2; j ++) { for (int k = j + 1; k <= s.len  1; k ++) { // Here, i, j, k are the three points' position. } } }

Based on @user20 suggestion, using 3 forloops
vector<string> restoreIpAddress(string s) { vector<string> res; if (s.size() > 12  s.size() < 4) return res; for (int i=1; i<4; i++) { string first = s.substr(0, i); if (!isValid(first)) continue; for (int j=1; i+j < s.size() && j<4; j++) { string second = s.substr(i, j); if (!isValid(second)) continue; for (int k=1; i+j+k < s.size() && k<4; k++) { string third = s.substr(i+j, k); string fourth = s.substr(i+j+k); if (isValid(third) && isValid(fourth)) { string temp = first+"."+second+"."+third+"."+fourth; res.push_back(temp); } } } } return res; } bool isValid(string s) { if (s.size() > 1 && s[0] == '0') return false; if (stoi(s) <= 255 && stoi(s) >= 0) return true; else return false; }

Solution in Java, use 3 for loop:
public class Solution { public ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> result = new ArrayList<String>(); String tempIP = null; for (int i = 1;i<s.length();i++){ if(i<=3&&(s.length()i)<=9&&(s.length()i)>=3){ for (int j=i+1;j<s.length();j++){ if(ji<=3&&(s.length()j)<=6&&(s.length()i)>=2){ for (int k=j+1;k<s.length();k++){ if ((kj)<=3&&(s.length()k)<=3){ String n1 = s.substring(0, i); String n2 = s.substring(i, j); String n3 = s.substring(j, k); String n4 = s.substring(k, s.length()); if (!(n1.charAt(0) =='0'&& n1.length()>1)&& !(n2.charAt(0) =='0'&& n2.length()>1)&& !(n3.charAt(0) =='0'&& n3.length()>1)&& !(n4.charAt(0) =='0'&& n4.length()>1)&& Integer.parseInt(n1)<256&&Integer.parseInt(n2)<256&& Integer.parseInt(n3)<256&&Integer.parseInt(n4)<256){ tempIP = n1+"."+n2+"."+n3+"."+n4; result.add(tempIP); } } } } } } } return result; }
}

Recursive version using Back Tracking.It is needed to insert 3 dots to divide the string, and need to make sure that IP address is valid..
Valid IP Address: less than or equal to 255, greater or equal to 0
"0X" or "00X" is not valid.
Sub net refers to the part of Ip address separated by a '.', in the string 255.255.324.54 there are four sub nets 255, 255, 324, 54.
For this one, the length of each sub net is from 1 to 3. We use a vector<string> to store each part, and cut the input string every time and append '.' for the first three sub nets, and then append the last sub net and do it recursively
Time complexity cannot be defined in big Oh notation as it tries to find the time complexity asymptotically but here the size of input is fixed between 4 and 12, and relative to input which is of constant size,the time taken by this program doesn't go linearly with the size of input, in fact if one plot a graph by taking input string length on X axis(values from 4 to 12 only) and and time complexity on Y axis the graph would be a straight line.
Space complexity cannot be defined in big Oh notation because relative to input string length of fixed size the size of the output list is also fixed in length .
class Solution { public: bool valid(string str){ //value of subnet must be in range 0 to 255 if (str.size()==3 && stoi(str)>255){return false;} //00X is invalid if (str.size()==3 && str[0]=='0'){return false;} //0X is invalid if (str.size()==2 && str[0]=='0'){return false;} return true; } void getIpAddresses(string s, string IpAddress, vector<string> &IpAddresses, int subnetLength){ if (subnetLength==0){ //sinput string is completely traversed add Ip address to list if (s.empty()){IpAddresses.push_back(IpAddress);} return; }else{ for (int i=1;i<=3;i++){ //check for the validity of the subnet if (s.size()>=i && valid(s.substr(0,i))){ //for the last subnet (subnetLength = 1) '.' shouldn't be appended if (subnetLength==1){getIpAddresses(s.substr(i),IpAddress+s.substr(0,i),IpAddresses,subnetLength1);} //for the subnets 2,3,4 the first three subnets '.' need to be appended. else{getIpAddresses(s.substr(i),IpAddress+s.substr(0,i)+".",IpAddresses,subnetLength1);} } } } } vector<string> restoreIpAddresses(string s) { vector<string> IpAddresses; //subnetLength helps to decide whether to append '.' or not last subnet shouldn't end with '.' int subnetLength = 4; getIpAddresses(s,"",IpAddresses,subnetLength); return IpAddresses; } };

It's my solution with java.It's based enumerate all the possible.
public class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<String>(); for(int i = 1; i < s.length(); ++i){ if(Integer.valueOf(s.substring(0, i))>255) break; if(i != 1 &&s.charAt(0) == '0') continue; for(int j = i+1; j < s.length(); ++j){ if(Integer.valueOf(s.substring(i, j))>255) break; if(ji != 1 &&s.charAt(i) == '0') continue; for(int k = j+1; k < s.length(); ++k){ if(Integer.valueOf(s.substring(j, k))>255) break; if(kj != 1 &&s.charAt(j) == '0') continue; try{ Integer.valueOf(s.substring(k)); }catch(Exception e){ continue; } if(Integer.valueOf(s.substring(k))>255){ continue; } if(s.length()k != 1 &&s.charAt(k) == '0') continue; res.add(s.substring(0, i)+"."+s.substring(i, j)+"."+s.substring(j, k) +"."+s.substring(k)); } } } return res; } }