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)
Note: according to the feedback from the test cases, any part that is in the form of '0x' or '0xx' is not valid.
Recursion: Using DFS
from http://blog.csdn.net/u011095253/article/details/9158449
http://www.shuatiblog.com/blog/2014/05/24/Restore-IP-Addresses/
http://www.jyuan92.com/blog/leetcode-restore-ip-addresses/
http://www.programcreek.com/2014/06/leetcode-restore-ip-addresses-java/
http://bangbingsyb.blogspot.com/2014/11/leetcode-restore-ip-addresses.html
public List<String> restoreIpAddresses(String s) { List<String> ret = new LinkedList<>(); int[] path = new int[4]; helper(ret, s, 0, path, 0); return ret; } void helper(List<String> acc, String s, int idx, int[] path, int segment){ if(segment == 4 && idx == s.length() ){ acc.add(path[0] + "." + path[1] + "."+ path[2] + "." + path[3]); return ; }else if(segment == 4 || idx == s.length() ){ return ; } for(int len = 1; len <= 3 && idx + len <= s.length() ; len ++){ int val = Integer.parseInt(s.substring(idx, idx + len)); // range check, no leading 0. if(val > 255 || len >= 2 && s.charAt(idx) == '0') break; path[segment] = val; helper(acc, s, idx + len, path, segment + 1); path[segment] = -1; // for debug. not needed } }
X. Iterative Version:
https://discuss.leetcode.com/topic/6304/my-concise-ac-java-code
https://discuss.leetcode.com/topic/3919/my-code-in-java
static List<String> restoreIpAddresses(String s) { List<String> ans = new ArrayList<String>(); int len = s.length(); for (int i = 1; i <=3; ++i){ // first cut if (len-i > 9) continue; for (int j = i+1; j<=i+3; ++j){ //second cut if (len-j > 6) continue; for (int k = j+1; k<=j+3 && k<len; ++k){ // third cut int a,b,c,d; // the four int's seperated by "." a = Integer.parseInt(s.substring(0,i)); b = Integer.parseInt(s.substring(i,j)); // notice that "01" can be parsed into 1. Need to deal with 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; // this is to reject those int's parsed from "01" or "00"-like substrings ans.add(ip); } } } return ans; }
http://www.darrensunny.me/leetcode-restore-ip-addresses/
Alternatively, we can consider each part iteratively by explicitly determining the positions of the dots.
vector<string> restoreIpAddresses(string s) { vector<string> ret; string ans; 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.length()) { int A = stoi(s.substr(0, a)); int B = stoi(s.substr(a, b)); int C = stoi(s.substr(a+b, c)); int D = stoi(s.substr(a+b+c, d)); if (A<=255 && B<=255 && C<=255 && D<=255) if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3) ret.push_back(ans); } return ret; }
Also refer to http://yucoding.blogspot.com/2013/04/leetcode-question-83-restore-ip.html
Read full article from LeetCode - Restore IP Addresses | Darren's Blog
For example: given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Note: according to the feedback from the test cases, any part that is in the form of '0x' or '0xx' is not valid.
Recursion: Using DFS
from http://blog.csdn.net/u011095253/article/details/9158449
0-255的数字,转换成字符,即每个Part 可能由一个字符组成,二个字符组成,或者是三个字符组成。那这又成为组合问题了,dfs便呼之欲出
所以我们写一个For循环每一层从1个字符开始取一直到3个字符,再加一个isValid的函数来验证取的字符是否是合法数字,如果是合法的数字,我们再进行下一层递归,否则跳过。
Maybe we can convert String to list first.
https://discuss.leetcode.com/topic/24184/backtracking-solution-in-java-easy-to-understand/2Maybe we can convert String to list first.
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if(s == null || s.length() == 0 || s.length() > 12) {
return res;
}
helper(s, res, new StringBuilder(), 0, 0);
return res;
}
private void helper(String s, List<String> res, StringBuilder sb, int pos, int count) {
if(pos == s.length() && count == 3) {
res.add(sb.toString());
return;
}
if(count == 3 || pos == s.length()) {
return;
}
for(int i = pos; i < s.length(); i++) {
String t = s.substring(pos, i+1);
if(t.length() > 3 || t.length() > 1 && t.charAt(0) == '0' || Integer.valueOf(t) > 255) {
break;
}
int len = sb.length();
sb.append(t);
if(i+1 != s.length()) {
sb.append(".");
helper(s, res, sb, i+1, count+1);
} else {
helper(s, res, sb, i+1, count);
}
sb.setLength(len);
}
}
https://discuss.leetcode.com/topic/34366/java-recursive-backtracking-easy-to-readpublic List<String> restoreIpAddresses(String s) {
List<String> ret = new LinkedList<>();
int[] path = new int[4];
helper(ret, s, 0, path, 0);
return ret;
}
void helper(List<String> acc, String s, int idx, int[] path, int segment){
if(segment == 4 && idx == s.length() ){
acc.add(path[0] + "." + path[1] + "."+ path[2] + "." + path[3]);
return ;
}else if(segment == 4 || idx == s.length() ){
return ;
}
for(int len = 1; len <= 3 && idx + len <= s.length() ; len ++){
int val = Integer.parseInt(s.substring(idx, idx + len));// not good
// range check, no leading 0.
if(val > 255 || len >= 2 && s.charAt(idx) == '0')
break;
path[segment] = val;
helper(acc, s, idx + len, path, segment + 1);
path[segment] = -1; // for debug.
}
}
https://discuss.leetcode.com/topic/41384/simple-java-solution-beating-100-of-java-submissionsprivate static final char DOT = '.';
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<String>();
char[] digits = s.toCharArray();
int len = s.length();
char[] currIpAddr = new char[len+3];
int pos = 0;
generateIpAddresses(digits, 4, 0, len, currIpAddr, pos, result);
return result;
}
private void generateIpAddresses(char[] digits, int remSegs, int start, int len,
char[] currIpAddr, int pos, List<String> result) {
if(start == len && remSegs == 0) {
result.add(String.valueOf(currIpAddr));
return;
}
//1. Checks for length of s too small
//2. Maximum Length of the remaining segments. Since a sgemnt can be upto 3 digits
// Length can not exceed 3x the remaining segments.
//3. Minimum Length of s. Each segment has to be atleast 1 digit
if((start > len) || ((len - start) > (3 * remSegs)) || ((len - start) < remSegs))
return;
if(remSegs < 4)
currIpAddr[pos++] = DOT;
int num = 0;
for(int i = 0; i < Math.min(len-start, 3);i++) {
num = (10*num) + (int)(digits[start+i] - '0');//\\
if(i > 0 && num < 10)// leading 0 cases i = 1, then the number should be > 10.
return;
////"010010"
//Valid: ["0.10.0.10","0.100.1.0"]
//Invalid: ["0.1.0.010","0.1.00.10","0.1.001.0","0.10.0.10","0.10.01.0","0.100.1.0",
//"01.0.0.10","01.0.01.0","01.00.1.0","010.0.1.0"]
if(num <= 255) {
currIpAddr[pos+i] = digits[start+i];
generateIpAddresses(digits, remSegs-1, start+i+1, len, currIpAddr, pos+i+1, result);
}
}
}
http://www.shuatiblog.com/blog/2014/05/24/Restore-IP-Addresses/
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
if (s.length()<4||s.length()>12) return res;
dfs(s,"",res,0);
return res;
}
public void dfs(String s, String tmp, ArrayList<String> res, int count){
if (count == 3 && isValid(s)) {
res.add(tmp + s);
return;
}
for(int i=1; i<4 && i<s.length(); i++){
String substr = s.substring(0,i);
if (isValid(substr)){
dfs(s.substring(i), tmp + substr + '.', res, count+1);
}
}
}
public boolean isValid(String s){
if (s.charAt(0)=='0') return s.equals("0");
int num = Integer.parseInt(s);
return num<=255 && num>0;
}
https://discuss.leetcode.com/topic/4742/very-simple-dfs-solutionhttp://www.jyuan92.com/blog/leetcode-restore-ip-addresses/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public List<String> restoreIpAddresses(String s) {
List<String> res = new LinkedList<String>();
if (null == s || s.length() < 4 || s.length() > 12) {
return res;
}
helper(res, s, new LinkedList<String>(), 0);
return res;
}
private void helper(List<String> res, String s, List<String> list, int count) {
if (list.size() == 4) {
if (count == s.length()) {
StringBuilder sb = new StringBuilder();
for (String ip : list) {
sb.append(ip);
sb.append(".");
}
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
}
return;
}
for (int i = count; i <= count + 3 && i < s.length(); i++) {
String temp = s.substring(count, i + 1);
if (isValid(temp)) {
list.add(temp);
helper(res, s, list, i + 1);
list.remove(list.size() - 1);
}
}
}
|
- Here, we should realise that there is no need to do Backtracking after recursive, because every time when you do operation on String, it will create a new String rather than the original one.
- after recurive the first three part, we can just using the remain string to check for the fourth part
public List<String> restoreIpAddresses2(String s) {
List<String> res = new LinkedList<String>();
if (null == s || s.length() < 4 || s.length() > 12) {
return res;
}
helper2(res, s, "", 0);
return res;
}
private void helper2(List<String> res, String s, String str, int count) {
if (count == 3 && isValid(s)) {
res.add(str + s);
return;
}
for (int i = 0; i < s.length() - 1 && i <= 3; i++) {
String temp = s.substring(0, i + 1);
if (isValid(temp)) {
helper2(res, s.substring(i + 1), str + temp + ".", count + 1);
}
}
}
http://www.jiuzhang.com/solutions/restore-ip-addresses/public ArrayList<String> restoreIpAddresses(String s) { ArrayList<String> result = new ArrayList<String>(); ArrayList<String> list = new ArrayList<String>(); if(s.length() <4 || s.length() > 12) return result; helper(result, list, s , 0); return result; } public void helper(ArrayList<String> result, ArrayList<String> list, String s, int start){ if(list.size() == 4){ if(start != s.length()) return; StringBuffer sb = new StringBuffer(); for(String tmp: list){ sb.append(tmp); sb.append("."); } sb.deleteCharAt(sb.length()-1); result.add(sb.toString()); return; } for(int i=start; i<s.length() && i<= start+3; i++){ String tmp = s.substring(start, i+1); if(isvalid(tmp)){ list.add(tmp); helper(result, list, s, i+1); list.remove(list.size()-1); } } } private boolean isvalid(String s){ if(s.charAt(0) == '0') return s.equals("0"); // to eliminate cases like "00", "10" int digit = Integer.valueOf(s); return digit >= 0 && digit <= 255; }
http://www.programcreek.com/2014/06/leetcode-restore-ip-addresses-java/
public List<String> restoreIpAddresses(String s) { ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>(); ArrayList<String> t = new ArrayList<String>(); dfs(result, s, 0, t); ArrayList<String> finalResult = new ArrayList<String>(); for(ArrayList<String> l: result){ StringBuilder sb = new StringBuilder(); for(String str: l){ sb.append(str+"."); } sb.setLength(sb.length() - 1); finalResult.add(sb.toString()); } return finalResult; } public void dfs(ArrayList<ArrayList<String>> result, String s, int start, ArrayList<String> t){ //if already get 4 numbers, but s is not consumed, return if(t.size()>=4 && start!=s.length()) return; //make sure t's size + remaining string's length >=4 if((t.size()+s.length()-start+1)<4) return; //t's size is 4 and no remaining part that is not consumed. if(t.size()==4 && start==s.length()){ ArrayList<String> temp = new ArrayList<String>(t); result.add(temp); return; } for(int i=1; i<=3; i++){ //make sure the index is within the boundary if(start+i>s.length()) break; String sub = s.substring(start, start+i); //handle case like 001. i.e., if length > 1 and first char is 0, ignore the case. if(i>1 && s.charAt(start)=='0'){ break; } //make sure each number <= 255 if(Integer.valueOf(sub)>255) break; t.add(sub); dfs(result, s, start+i, t); t.remove(t.size()-1); } |
于以s[i]开头的数字有3种可能:
1. s[i]
2. s[i : i+1],s[i] !=0时
3. s[i : i+2],s[i] != 0,且s[i : i+2] <= 255
bool isValidNum(string s) { if(s.empty() || s.size()>3) return false; if(s[0]=='0' && s.size()!=1) return false; if(s.size()==3 && stoi(s)>255) return false; return true; }https://leetcode.com/discuss/80435/java-recursive-backtracking-easy-to-read
public List<String> restoreIpAddresses(String s) { List<String> ret = new LinkedList<>(); int[] path = new int[4]; helper(ret, s, 0, path, 0); return ret; } void helper(List<String> acc, String s, int idx, int[] path, int segment){ if(segment == 4 && idx == s.length() ){ acc.add(path[0] + "." + path[1] + "."+ path[2] + "." + path[3]); return ; }else if(segment == 4 || idx == s.length() ){ return ; } for(int len = 1; len <= 3 && idx + len <= s.length() ; len ++){ int val = Integer.parseInt(s.substring(idx, idx + len)); // range check, no leading 0. if(val > 255 || len >= 2 && s.charAt(idx) == '0') break; path[segment] = val; helper(acc, s, idx + len, path, segment + 1); path[segment] = -1; // for debug. not needed } }
X. Iterative Version:
https://discuss.leetcode.com/topic/6304/my-concise-ac-java-code
the basic idea is to make three cuts into the string, separating it into four parts, each part contains 1~3 digits and it must be <255.
https://discuss.leetcode.com/topic/3919/my-code-in-java
3-loop divides the string s into 4 substring: s1, s2, s3, s4. Check if each substring is valid. In isValid, strings whose length greater than 3 or equals to 0 is not valid; or if the string's length is longer than 1 and the first letter is '0' then it's invalid; or the string whose integer representation greater than 255 is invalid.
-- not efficient as the one below. - if s1 is not valid, no need to continue
public List<String> restoreIpAddresses(String s) {
List<String> res = 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++){
String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len);
if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
res.add(s1+"."+s2+"."+s3+"."+s4);
}
}
}
}
return res;
}
public boolean isValid(String s){
if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255)
return false;
return true;
}
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
if (s.length() > 12 || s.length() < 4) return res;
for (int i = 1; i < 4; i ++) {
String first = s.substring(0, i);
if (! isValid(first)) continue;
for (int j = 1; i + j < s.length() && j < 4; j ++) {
String second = s.substring(i, i + j);
if (! isValid(second)) continue;
for (int k = 1; i + j + k < s.length() && k < 4; k ++) {
String third = s.substring(i + j, i + j + k);
String fourth = s.substring(i + j + k);
if (isValid(third) && isValid(fourth))
res.add(first + "." + second + "." + third + "." + fourth);
}
}
}
return res;
}
https://leetcode.com/discuss/19296/my-concise-ac-java-codestatic List<String> restoreIpAddresses(String s) { List<String> ans = new ArrayList<String>(); int len = s.length(); for (int i = 1; i <=3; ++i){ // first cut if (len-i > 9) continue; for (int j = i+1; j<=i+3; ++j){ //second cut if (len-j > 6) continue; for (int k = j+1; k<=j+3 && k<len; ++k){ // third cut int a,b,c,d; // the four int's seperated by "." a = Integer.parseInt(s.substring(0,i)); b = Integer.parseInt(s.substring(i,j)); // notice that "01" can be parsed into 1. Need to deal with 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; // this is to reject those int's parsed from "01" or "00"-like substrings ans.add(ip); } } } return ans; }
http://www.darrensunny.me/leetcode-restore-ip-addresses/
Alternatively, we can consider each part iteratively by explicitly determining the positions of the dots.
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> result = new ArrayList<String>();
if (s == null)
return result;
int n = s.length();
if (n < 4 || n > 12)
return result;
// For each possible first part
for (int i = 1; i <= 3; i++) { // At most three digits at each part
if (n-i > 9) // The number of digits for remaining three parts should not exceed 9
continue;
if (s.charAt(0) == '0' && i > 1) // 0x or 0xx is not allowed
break;
String first = s.substring(0, i); // String before the first dot
if (Integer.parseInt(first) <= 255) { // The first part is within proper range
// For each possible second part given the first part
for (int j = i+1; j <= i+3 && j < n; j++) {
if (n-j > 6) // The number of digits for remaining two parts should not exceed 6
continue;
if (s.charAt(i) == '0' && j > i+1)
break;
String second = s.substring(i, j); // String after the first dot and before the second
if (Integer.parseInt(second) <= 255) { // The second part is within proper range
// For each possible third part given the second part
for (int k = j+1; k <= j+3 && k < n; k++) {
if (n-k > 3) // The number of digits for remaining part should not exceed 3
continue;
if (s.charAt(j) == '0' && k > j+1)
break;
String third = s.substring(j, k); // String after the second dot and before the third
if (Integer.parseInt(third) <= 255) { // The third part is within proper range
// If the fourth part is a single digit, or it does not begin with a '0' and
// it is within proper range, we have got a valid IP address
if (k == n-1 || s.charAt(k) != '0' && Integer.parseInt(s.substring(k)) <= 255)
result.add(first+'.'+second+'.'+third+'.'+s.substring(k));
}
}
}
}
}
}
return result;
}
https://leetcode.com/discuss/88736/who-can-beat-this-codevector<string> restoreIpAddresses(string s) { vector<string> ret; string ans; 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.length()) { int A = stoi(s.substr(0, a)); int B = stoi(s.substr(a, b)); int C = stoi(s.substr(a+b, c)); int D = stoi(s.substr(a+b+c, d)); if (A<=255 && B<=255 && C<=255 && D<=255) if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3) ret.push_back(ans); } return ret; }
Also refer to http://yucoding.blogspot.com/2013/04/leetcode-question-83-restore-ip.html
Read full article from LeetCode - Restore IP Addresses | Darren's Blog