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， 所以不需要刪除一些已經(jīng)用過的東西。同時(shí)，他是分級的，當(dāng)?shù)竭_(dá)第四級時(shí)，就必須停止了。然后還有些corner case。
比如說，我規(guī)定這一級的 width = 3, 然后掃描出了， 017. 如果我調(diào)用Integer.parseInt 掃出來的就是17，這是對的。但是 017是錯誤的。應(yīng)該排除。
還有width =2 , 08 這些也是錯誤的。
還有可以及時(shí)停止掃描來節(jié)省時(shí)間。比如當(dāng)掃描到第二層時(shí)，如果后面的字符串長度只有1，那么不用操作了，這肯定是錯的，后面還有兩級呢。
如果后面的字符串長度 >6了，那也不需要掃描了，因?yàn)楹竺孀疃嘁簿?位數(shù)字。
然后排除掉這些corner case后，程序就會跑的這么快了。
**
下面說下，我剛才才注意到的一個知識點(diǎn)。其實(shí)一開始我的代碼不是這樣的， 或者說有個細(xì)節(jié)不是這樣的。也就是 ip + s.substring(begin, begin + width) 還是 ip + Integer.toString(ipPart); 其實(shí)兩個方法達(dá)到的效果是相通的，但算法復(fù)雜度完全不同。下面粘上用 toString() 測試的圖片。**
具體string這一塊其實(shí)有很多需要分析的。比如這里。
將一個 integer轉(zhuǎn)換成string，怎么樣更快？
Integer.toString(a); or String.valueOf(a); or String s = "" + a;
現(xiàn)在可以確定的是，最后一個很消耗資源。
http://it.deepinmind.com/java/2014/03/24/java-string-performance.html
有時(shí)間再好好研究下 string 吧。里面講究太多了。
**
總結(jié)： 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 時(shí)，需要考慮剩余長度不夠再做ip address，此時(shí)需要直接退出循環(huán)，break
k = 4 時(shí)，需要考慮剩余長度過長，不止3位了。此時(shí)也是退出dfs
需要考慮掃描出來的數(shù)字是否大于255.
需要考慮， 017 是不符合規(guī)定的，需要去除。
即任何以0開頭的數(shù)字，除了0自己，都是違規(guī)的。
然后就差不多了。
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);
}
}
}
自己寫了出來，感覺比以前的代碼簡潔多了。
為什么呢？
仔細(xì)觀察，發(fā)現(xiàn)我思考 backtracking 經(jīng)常有個問題。
什么時(shí)候截止 backtracking
比如這里， level = 3 (0-3) 時(shí)，就可以停止了，
但我需要在 level = 3時(shí)加判斷嗎？
不該，否則代碼會很復(fù)雜，和下部分代碼也有很多重復(fù)。
我應(yīng)該再下去一層，這才是底層。
所以backtracking 每一層的物理意義是，
這一層，我檢驗(yàn)過了，ok, 沒問題，下一層吧。
然后一層層下去。
如果這一層有問題，那么就返回。
如果走到最后一層，發(fā)現(xiàn)沒有問題了，那么就將最終結(jié)果插入到容器中。
就是這么個過程。
word pattern 2 也是如此。
還有就是，backtracking 用 stringbuilder 時(shí)，可以用 setLength
之類的辦法快速清除下一層給這層帶來的變化。
還有個細(xì)節(jié)需要注意。當(dāng)截下來的數(shù)字， > 255 或者，長度大于1卻以0開頭的話，都是無效的，直接 Ignore
Anyway, Good luck, Richardo! -- 09/19/2016
