RestoreIPAddress [source code]
public class RestoreIPAddress {
static
/******************************************************************************/
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<> ();
if (s.length () < 4 || s.length () > 12)
return res;
dfs (s.toCharArray (), 0, 0, new char[s.length () + 3], 0, 0, res);
return res;
}
// POS is the index in CHS to process in this iteration, IP_POS is the next index in IP to store something (number or dot)
// PREV stores the value up until this iteration that has not terminated by a dot
void dfs (char[] chs, int prev, int pos, char[] ip, int ip_pos, int dot_cnt, List<String> ls) {
// Order of base cases matters
if (pos >= chs.length)
return;
if (dot_cnt == 3) {
// do not && this header together in the outer if header
if (chs[pos] == '0' && pos < chs.length - 1)
return;
for (int i = pos; i < chs.length; i++)
prev = prev * 10 + chs[i] - '0';
if (prev < 256)
ls.add (new String (ip, 0, ip_pos) + Integer.toString (prev));
return;
}
int num = chs[pos] - '0', cur = prev * 10 + num;
// What can we place at this IP_POS?
if (cur == 0) {
// IP[IP_POS - 1] is a dot, and CHS[POS] is 0, we have to put down "0." in IP and move on
ip[ip_pos++] = chs[pos];
ip[ip_pos++] = '.';
dot_cnt++;
dfs (chs, 0, pos + 1, ip, ip_pos, dot_cnt, ls);
} else {
// Branching Choice: grow PREV by NUM to CUR or not: corresponds to 2 recursive calls
if (cur < 256) {
// we can grow PREV by NUM to CUR: put CHS[POS] down and move on
ip[ip_pos++] = chs[pos];
dfs (chs, cur, pos + 1, ip, ip_pos, dot_cnt, ls);
ip_pos--;
}
if (prev > 0) {
// We want to place dot here to end this PREV, but can only do so when PREV > 0
ip[ip_pos++] = '.';
dot_cnt++;
dfs (chs, 0, pos, ip, ip_pos, dot_cnt, ls);
}
}
}
}
/******************************************************************************/
public static void main(String[] args) {
RestoreIPAddress.Solution tester = new RestoreIPAddress.Solution();
String[][] inputs = {
{"25525511135"}, {"255.255.11.135", "255.255.111.35"},
{"0000"}, {"0.0.0.0"},
{"1111"}, {"1.1.1.1"},
{"010010"}, {"0.10.0.10","0.100.1.0"},
{"00000"}, {},
{"0690"}, {"0.6.9.0"},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
String s = inputs[2 * i][0];
Set<String> ans = new HashSet<> ();
for (String str : inputs[2 * i + 1])
ans.add (str);
List<String> output_ls = tester.restoreIpAddresses (s);
Set<String> output = new HashSet<> (output_ls);
System.out.printf ("%s -> %s, expected: %s\n",
s, Printer.wrap (output.toString (), output_ls.size () == output.size () && output.equals (ans) ? 92 : 91), ans
);
}
}
}
刚读完题目觉得很简单, 但是实际上写起来还是有点麻烦的;
突然想到, IP好像是可以包含0的? 这个估计就是这个题目的坑; 不过说实话, 就算是可以用0, 这个string本身也要包含0才行; 所以最后感觉其实并没有什么影响;
backtracking的题目需要画tree没有什么丢人的, 相反, 这个可能还会被面试官看成是会交流会展示自己的想法的表现;
这个题目做了好长时间, 都debug不出来, 主要还是稍微typical一点的test都太大了, tree非常的大; 就算是我用完整的debug手段, 最后的trace也是非常的overwhelming;
而且这个题目本身虽然看起来简单, 但是真的是打到了我backtracking问题里面的盲点了; 这个问题难点就在于对0等一系列小细节的处理, 稍微一不处理好, 整个逻辑全都错了; 设计逻辑的核心是要先事先想清楚你每一个state对应的是什么(state just before entering each node); 而因为这个题目DFS函数的参数相当的多(就算不包含那些collector), 所以导致这个state定义一点都不trivial;
被虐的惨兮兮, 终于还是做出来了, 速度是3ms (86%), 倒是没有想象中的快, 毕竟我是完全用array来accum的, 当然其实用StringBuilder可能会更方便一点. 这里是当时用来debug的版本:
class Solution {
String indent = "";
boolean MD = false;
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<> ();
if (s.length () < 4 || s.length () > 12)
return res;
dfs (s.toCharArray (), 0, 0, new char[s.length () + 3], 0, 0, res);
return res;
}
void dfs (char[] chs, int prev, int pos, char[] ip, int ip_pos, int dot_cnt, List<String> ls) {
String old_indent = indent, header = "";
if (MD) header = String.format ("prev:(%d), pos:(%d), ip_pos:(%d), dot_cnt:(%s), [%s], [%s], %s", prev, pos, ip_pos, wrap (dot_cnt + "", dot_cnt == 3 ? 91 : 0), pointArray (chs, new int[] {96}, new int[] {pos}), pointArray (ip, new int[] {95}, new int[] {ip_pos}), ls);
if (MD) indent += " ";
if (MD) System.out.printf ("%s%s\n", indent, header);
// Order of base cases matters
if (pos >= chs.length) {
indent = old_indent;
return;
}
if (dot_cnt == 3) {
for (int i = pos; i < chs.length; i++)
prev = prev * 10 + chs[i] - '0';
if (prev < 256 && !(prev > 0 && chs[pos] == '0') && !(prev == 0 && pos < chs.length - 1))
ls.add (new String (ip, 0, ip_pos) + Integer.toString (prev));
indent = old_indent;
return;
}
int num = chs[pos] - '0', cur = prev * 10 + num;
// What can we place at this IP_POS?
if (cur == 0) {
ip[ip_pos++] = chs[pos];
ip[ip_pos++] = '.';
dot_cnt++;
dfs (chs, 0, pos + 1, ip, ip_pos, dot_cnt, ls);
} else {
if (cur < 256) {
ip[ip_pos++] = chs[pos];
dfs (chs, cur, pos + 1, ip, ip_pos, dot_cnt, ls);
ip_pos--;
}
if (prev > 0) {
ip[ip_pos++] = '.';
dot_cnt++;
dfs (chs, 0, pos, ip, ip_pos, dot_cnt, ls);
}
}
indent = old_indent;
}
String pointArray (char[] nums, int[] codes, int[] indices) {
StringBuilder sb = new StringBuilder ();
int pos = 0;
for (int i = 0; i < nums.length; i++) {
if (pos < codes.length && i == indices[pos]) {
sb.append (wrap (nums[i] + "", codes[pos]));
pos++;
} else {
sb.append (nums[i]);
}
sb.append (" ");
}
return sb.toString ();
}
String wrap (String s, int code) {
return (char) 27 + "[" + code + "m" + s + (char) 27 + "[0m";
}
}
一个typical的trace:
prev:(0), pos:(0), ip_pos:(0), dot_cnt:(0), [0 6 9 0 ], [ ], []
prev:(0), pos:(1), ip_pos:(2), dot_cnt:(1), [0 6 9 0 ], [0 . ], []
prev:(6), pos:(2), ip_pos:(3), dot_cnt:(1), [0 6 9 0 ], [0 . 6 ], []
prev:(69), pos:(3), ip_pos:(4), dot_cnt:(1), [0 6 9 0 ], [0 . 6 9 ], []
prev:(0), pos:(3), ip_pos:(5), dot_cnt:(2), [0 6 9 0 ], [0 . 6 9 . ], []
prev:(0), pos:(4), ip_pos:(7), dot_cnt:(3), [0 6 9 0 ], [0 . 6 9 . 0 . ], []
prev:(0), pos:(2), ip_pos:(4), dot_cnt:(2), [0 6 9 0 ], [0 . 6 . . 0 . ], []
prev:(9), pos:(3), ip_pos:(5), dot_cnt:(2), [0 6 9 0 ], [0 . 6 . 9 0 . ], []
prev:(90), pos:(4), ip_pos:(6), dot_cnt:(2), [0 6 9 0 ], [0 . 6 . 9 0 . ], []
prev:(0), pos:(3), ip_pos:(6), dot_cnt:(3), [0 6 9 0 ], [0 . 6 . 9 . . ], []
0690 -> [0.6.9.0], expected: [0.6.9.0]
彩图版本:
后来把debug信息都删掉了之后, 就是最上面的这个版本, 这个版本倒是很快, 2ms (96%)的速度;
开始总结, 首先注意我对String(char[] value, int offset, int count)这个API的使用, 不是第一次了;
这个题目最后实际上比较难的是整体逻辑的设计, 可以看到body里面的代码就真的是不trivial, 想了好久; 根据prev, num, cur三者的情况, 仔细的分析; 刚开始我犯的一个严重的错误是, 比如我决定当前node drop dot, 那么意思就是不把[POS]放到PREV里面去, 但是我却在drop了dot之后, 又接着把[POS]给drop了, 当时的想法就是, 反正后面还是会继续drop这个[POS]的啊; 但是实际上这个是未必的, 假如你刚drop的是第三个dot, 然后后面整个就不valid呢? 你最后就会让base case处理起来很麻烦; 具体可以看之前的submission的代码, 简直是无法debug;
另外一个小的东西就是, 写recursion的时候, 当然参数要改动, 比如各种pos, 你的一个选择是, 你是直接用immutable的方式来写, 比如直接在当前iteration, ip_pos始终就不改变, 而是直接用类似ip_pos + 1这样的东西来操作array; 另外一种方法就是[pos++] = num这种最常见的思路; 我这里其实自己开发的时候两种思路都采取过; 最后感觉还是这个思路直观一些: 你只要脑子里面有当前的state对应的pos的位置就行了; 最怕的就是你两种一起混着用, 这个我还真用过了; 有点给自己加难度的意思, 尤其是有时间压力的时候, 这种混淆的notation, 很容易就把自己脑子给搞混了;
写的时候要死要活, 写完了也想不起来当时怎么被虐的感想了; 反正, 这个题目最好后面还是重新多看一看;
没有editorial;
https://leetcode.com/problems/restore-ip-addresses/discuss/30949/My-code-in-Java
public class Solution {
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;
}
}
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.
其实后面想的时间长了之后也是感觉到我估计是把题目想复杂了, 然后重新找思考方向, 也是大概想到了这里这个类似的, 直接divide的思路; 没想到discussion里面果然大部分都是这个思路;
看了一下之后, 这个方法真的可以说是很脏了; 感觉想到这个思路的一个关键点, 是先想要对每一个数字分段进行一个validate的操作; 能够想到把这个valid的概念给抽象出来之后, 想到这个思路其实也不是特别困难;
Thanks for your sharing. But I think DFS is more elegant and concise.
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
doRestore(result, "", s, 0);
return result;
}
private void doRestore(List<String> result, String path, String s, int k) {
if (s.isEmpty() || k == 4) {
if (s.isEmpty() && k == 4)
result.add(path.substring(1));
return;
}
for (int i = 1; i <= (s.charAt(0) == '0' ? 1 : 3) && i <= s.length(); i++) { // Avoid leading 0
String part = s.substring(0, i);
if (Integer.valueOf(part) <= 255)
doRestore(result, path + "." + part, s.substring(i), k + 1);
}
}
啊, 这个算法也很漂亮, 关键写起来还比我的简单很多; 我感觉我这题还是太执迷于纯粹的char操作的解法, 最后有点限制思路了; 他这里, 其实就是一个size based的, 总共只有4个level, 每一个level, 选择一个substring就行了, 然后加了一点valid的判断, 非常的简单化;
我这个prev的算法, 其实就有点类似分段算法, 感觉我对于分段算法这种莫问前程的思路还是太执着了; 他们这种思路就是, 老子偏要问;
看这些别人写的recursive代码的时候, 也要先看核心逻辑, 不要因为base case写在前面就先看base case;
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<String>();
if(s.length() < 4 || s.length() > 12)
return result;
restoreIpAddresses(s, 0, 4, result, new StringBuilder());
return result;
}
public void restoreIpAddresses(String s, int index, int set, List<String>result, StringBuilder sb){
if(index > s.length() || s.length() - index < set ||s.length() - index > set*3){
return;
}else if(index == s.length()){
sb.setLength(sb.length()-1);
result.add(sb.toString());
return;
}
int len = sb.length();
for(int i = 1; i <=3 ; i++){
if(index+i <= s.length() &&
(i!=3 || Integer.parseInt(s.substring(index, index+i))< 256) &&
(i==1 || Integer.parseInt(s.substring(index, index+1))!= 0))
{
sb.append(s.substring(index, index+i)+".");
restoreIpAddresses(s, index+i, set-1, result, sb);
sb.setLength(len);
}
}
}
}
还是类似的思路, 都是站在一个位置考虑可以选择的substring有哪些;
https://leetcode.com/problems/restore-ip-addresses/discuss/30972/WHO-CAN-BEAT-THIS-CODE
// c++ code
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;
}
跟前面那个是一样的;
注意他这个直接用length来判断valid的思路还是挺新颖的; 好像大部分不合理的, 比如01这样的字段, 都是可以通过parse之后的length来排除掉的(length会变短); 基本上就是利用了parse的自动trim leading 0的功能;
You can improve performance in quite a few ways:
- If length of string is 12, you don’t need all those loops and length of A B C D all will be 3 always. Similarly if length of string is 10 then for case when you consider length of A as 1 then length B,C,D will be always 3.
- Instead of calculating A,B,C,D all at once, calculate one and check one, this will be better for performance. like in case string is “25525511222” here according to code 1st value of A will be “2” and B will be “552” which is invalid you don’t need rest of calculations in this case.
https://leetcode.com/problems/restore-ip-addresses/discuss/30944/Very-simple-DFS-solution
public List<String> restoreIpAddresses(String s) {
List<String> solutions = new ArrayList<String>();
restoreIp(s, solutions, 0, "", 0);
return solutions;
}
private void restoreIp(String ip, List<String> solutions, int idx, String restored, int count) {
if (count > 4) return;
if (count == 4 && idx == ip.length()) solutions.add(restored);
for (int i=1; i<4; i++) {
if (idx+i > ip.length()) break;
String s = ip.substring(idx,idx+i);
if ((s.startsWith("0") && s.length()>1) || (i==3 && Integer.parseInt(s) >= 256)) continue;
restoreIp(ip, solutions, idx+i, restored+s+(count==3?"" : "."), count+1);
}
}
代码写的很利落; 基本思路还是一个height4的tree;
Neat solution! Thanks!
Another implementation with minor modifications.
// Requirements of IP adresses:
// (1) No section can start with a 0 expect 0 itself
// (2) No section can exceed 256
// (3) Have to have exactly 4 sections
public List<String> restoreIpAddresses(String s) {
List<String> ips = new ArrayList<>();
char[] arr = s.toCharArray();
restoreIpAddresses(arr, 0, new StringBuilder(), ips, 0);
return ips;
}
private void restoreIpAddresses(char[] arr, int startIdx, StringBuilder ip, List<String> ips, int count){
if(count > 4) return;
if(count == 4){
if(startIdx == arr.length){
ips.add(ip.toString());
}
return;
}
int num = 0, ipLen = ip.length();
for(int i = startIdx; i <= startIdx+3 && i < arr.length; i++){
num = num*10 + arr[i]-'0';
if(num >= 256) break;
ip.append(num);
if(count != 3) ip.append('.'); // the last section should not append '.'
restoreIpAddresses(arr, i+1, ip, ips, count+1);
ip.setLength(ipLen);
if(num == 0) break; // if num starts with 0, only allows a single 0
}
}
小的优化, 比如不可能用substring+parse而是要自己算数字等等; 不过他对于IP的定义还是值得看一下;
https://leetcode.com/problems/restore-ip-addresses/discuss/30998/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.
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;
}
这个解法也用了parse之后的length和s.length () + 3对比的技巧;
submission应该是没有更好的了;
另外一个也是2ms的解法;
class Solution {
public void helper(List<String> ret, String s, int pos, int[] curr, int ind){
if(ind==4 && pos==s.length()){
StringBuilder sb = new StringBuilder();
for(int i=0;i<4;i++){
if(sb.length()>0) sb.append('.');
sb.append(curr[i]);
}
ret.add(sb.toString());
}else if(ind<4 && pos<s.length()){
int n = 0;
for(int i=pos;i<s.length() && i<pos+3;i++){
n*=10;
n+=(s.charAt(i)-'0');
if(n>255) return ;
curr[ind] = n;
helper(ret,s,i+1,curr,ind+1);
if(n==0) return;
}
curr[ind] = 0;
}
}
public List<String> restoreIpAddresses(String s) {
List<String> ret = new ArrayList<>();
helper(ret,s,0,new int[4], 0);
return ret;
}
}
就是上面那个height4的做法, 不过全都转换成int计算, 最后输出的时候才换回去到string;
Problem Description
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)
Difficulty:Medium
Total Accepted:99.2K
Total Submissions:351.1K
Contributor:LeetCode
Related Topics
stringbacktracking
Similar Questions
IP to CIDR