My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> restoreIpAddresses(String s) {
if (s == null)
return null;
ArrayList<String> result = new ArrayList<String>();
if (s.length() < 4 || s.length() > 12)
return result;
restoreIpAddresses(s, "", 0, 0, 0, result);
return result;
}
private void restoreIpAddresses(String s, String ip, int begin, int width, int level,
ArrayList<String> result) {
if (begin + width - 1 >= s.length())
return;
else if (level == 4) {
if (s.length() - begin - width > 0)
return;
int ipPart = Integer.parseInt(s.substring(begin, begin + width));
if (width == 3 && ipPart < 100)
return;
else if (width == 2 && ipPart < 10)
return;
else if (ipPart > 255)
return;
else {
result.add(ip + Integer.toString(ipPart));
return;
}
}
else if (level == 0) {
for (int i = 1; i < 4; i++)
restoreIpAddresses(s, ip, begin + width, i, level + 1, result);
}
else {
int residueIp = s.length() - begin - width;
if (residueIp < 4 - level || residueIp > 3 * (4 - level))
return;
int ipPart = Integer.parseInt(s.substring(begin, begin + width));
if (width == 3 && ipPart < 100)
return;
else if (width == 2 && ipPart < 10)
return;
else if (ipPart > 255)
return;
ip += Integer.toString(ipPart) + ".";
for (int i = 1; i < 4; i++)
restoreIpAddresses(s, ip, begin + width, i, level + 1, result);
}
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.restoreIpAddresses("101023"));
}
}
My test result:
这道题目和之前 Array里面的 permutation等等很像。不同的是，他只需要插入符合要求的字符串，不需要插入ArrayList， 所以不需要删除一些已经用过的东西。同时，他是分级的，当到达第四级时，就必须停止了。然后还有些corner case。
比如说，我规定这一级的 width = 3, 然后扫描出了， 017. 如果我调用Integer.parseInt 扫出来的就是17，这是对的。但是 017是错误的。应该排除。
还有width =2 , 08 这些也是错误的。
还有可以及时停止扫描来节省时间。比如当扫描到第二层时，如果后面的字符串长度只有1，那么不用操作了，这肯定是错的，后面还有两级呢。
如果后面的字符串长度 >6了，那也不需要扫描了，因为后面最多也就6位数字。
然后排除掉这些corner case后，程序就会跑的这么快了。
**
下面说下，我刚才才注意到的一个知识点。其实一开始我的代码不是这样的， 或者说有个细节不是这样的。也就是 ip + s.substring(begin, begin + width) 还是 ip + Integer.toString(ipPart); 其实两个方法达到的效果是相通的，但算法复杂度完全不同。下面粘上用 toString() 测试的图片。**
具体string这一块其实有很多需要分析的。比如这里。
将一个 integer转换成string，怎么样更快？
Integer.toString(a); or String.valueOf(a); or String s = "" + a;
现在可以确定的是，最后一个很消耗资源。
http://it.deepinmind.com/java/2014/03/24/java-string-performance.html
有时间再好好研究下 string 吧。里面讲究太多了。
**
总结： String， backtracing, Permutation thinking
**
Anyway, Good luck, Richardo!
My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> restoreIpAddresses(String s) {
ArrayList<String> ret = new ArrayList<String>();
if (s == null || s.length() < 4)
return ret;
helper(0, 1, s, new StringBuilder(), ret);
return ret;
}
private void helper(int begin, int k, String s, StringBuilder ip, ArrayList<String> ret) {
if (k == 4) {
if (s.length() - begin > 3)
return;
if (s.charAt(begin) == '0' && s.length() - begin >= 2)
return;
int tmp = Integer.parseInt(s.substring(begin, s.length()));
if (tmp > 255)
return;
int len = ip.length();
ip.append(tmp);
ret.add(ip.toString());
ip.delete(len, ip.length());
}
else {
for (int i = 1; i <= 3; i++) {
if (s.length() - (begin + i) < (4 - k))
break;
if (s.charAt(begin) == '0' && i >= 2)
break;
int tmp = Integer.parseInt(s.substring(begin, begin + i));
if (tmp > 255)
continue;
int len = ip.length();
ip.append(String.valueOf(tmp) + ".");
helper(begin + i, k + 1, s, ip, ret);
ip.delete(len, ip.length());
}
}
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.restoreIpAddresses("010010"));
}
}
这道题目还是挺烦的。
有几个corner case需要考虑。
首先，分成k < 4 和 k = 4两种情况。
k < 4 时，需要考虑剩余长度不够再做ip address，此时需要直接退出循环，break
k = 4 时，需要考虑剩余长度过长，不止3位了。此时也是退出dfs
需要考虑扫描出来的数字是否大于255.
需要考虑， 017 是不符合规定的，需要去除。
即任何以0开头的数字，除了0自己，都是违规的。
然后就差不多了。
Anyway, Good luck, Richardo!
My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> ret = new ArrayList<String>();
if (s == null || s.length() == 0 || s.length() > 12) {
return ret;
}
helper(0, s, new StringBuilder(), 0, ret);
return ret;
}
private void helper(int begin, String s, StringBuilder ip, int level, List<String> ret) {
if (begin >= s.length()) {
if (level == 4) {
ret.add(ip.deleteCharAt(ip.length() - 1).toString());
}
return;
}
int len = ip.length();
for (int i = begin; i < begin + 3 && i < s.length(); i++) {
String part = s.substring(begin, i + 1);
int temp = Integer.parseInt(part);
if (temp >= 256) {
continue;
}
else if (part.charAt(0) == '0' && i > begin) {
continue;
}
ip.append(part + ".");
helper(i + 1, s, ip, level + 1, ret);
ip.setLength(len);
}
}
}
自己写了出来，感觉比以前的代码简洁多了。
为什么呢？
仔细观察，发现我思考 backtracking 经常有个问题。
什么时候截止 backtracking
比如这里， level = 3 (0-3) 时，就可以停止了，
但我需要在 level = 3时加判断吗？
不该，否则代码会很复杂，和下部分代码也有很多重复。
我应该再下去一层，这才是底层。
所以backtracking 每一层的物理意义是，
这一层，我检验过了，ok, 没问题，下一层吧。
然后一层层下去。
如果这一层有问题，那么就返回。
如果走到最后一层，发现没有问题了，那么就将最终结果插入到容器中。
就是这么个过程。
word pattern 2 也是如此。
还有就是，backtracking 用 stringbuilder 时，可以用 setLength
之类的办法快速清除下一层给这层带来的变化。
还有个细节需要注意。当截下来的数字， > 255 或者，长度大于1却以0开头的话，都是无效的，直接 Ignore
Anyway, Good luck, Richardo! -- 09/19/2016
