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厢破， 所以不需要?jiǎng)h除一些已經(jīng)用過(guò)的東西荣瑟。同時(shí)，他是分級(jí)的摩泪，當(dāng)?shù)竭_(dá)第四級(jí)時(shí)笆焰，就必須停止了。然后還有些corner case见坑。
比如說(shuō)仙辟，我規(guī)定這一級(jí)的 width = 3, 然后掃描出了， 017. 如果我調(diào)用Integer.parseInt 掃出來(lái)的就是17鳄梅，這是對(duì)的叠国。但是 017是錯(cuò)誤的。應(yīng)該排除戴尸。
還有width =2 , 08 這些也是錯(cuò)誤的粟焊。
還有可以及時(shí)停止掃描來(lái)節(jié)省時(shí)間。比如當(dāng)掃描到第二層時(shí)孙蒙，如果后面的字符串長(zhǎng)度只有1项棠，那么不用操作了，這肯定是錯(cuò)的挎峦，后面還有兩級(jí)呢香追。
如果后面的字符串長(zhǎng)度 >6了，那也不需要掃描了坦胶，因?yàn)楹竺孀疃嘁簿?位數(shù)字透典。
然后排除掉這些corner case后，程序就會(huì)跑的這么快了顿苇。
**
下面說(shuō)下峭咒，我剛才才注意到的一個(gè)知識(shí)點(diǎn)。其實(shí)一開(kāi)始我的代碼不是這樣的纪岁， 或者說(shuō)有個(gè)細(xì)節(jié)不是這樣的凑队。也就是 ip + s.substring(begin, begin + width) 還是 ip + Integer.toString(ipPart); 其實(shí)兩個(gè)方法達(dá)到的效果是相通的，但算法復(fù)雜度完全不同幔翰。下面粘上用 toString() 測(cè)試的圖片漩氨。**
具體string這一塊其實(shí)有很多需要分析的西壮。比如這里。
將一個(gè) integer轉(zhuǎn)換成string叫惊，怎么樣更快款青？
Integer.toString(a); or String.valueOf(a); or String s = "" + a;
現(xiàn)在可以確定的是，最后一個(gè)很消耗資源赋访。
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"));
}
}
這道題目還是挺煩的。
有幾個(gè)corner case需要考慮旋炒。
首先步悠，分成k < 4 和 k = 4兩種情況。
k < 4 時(shí)瘫镇，需要考慮剩余長(zhǎng)度不夠再做ip address鼎兽，此時(shí)需要直接退出循環(huán)，break
k = 4 時(shí)铣除，需要考慮剩余長(zhǎng)度過(guò)長(zhǎng)谚咬，不止3位了。此時(shí)也是退出dfs
需要考慮掃描出來(lái)的數(shù)字是否大于255.
需要考慮尚粘， 017 是不符合規(guī)定的择卦，需要去除。
即任何以0開(kāi)頭的數(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);
}
}
}
自己寫(xiě)了出來(lái)尚辑，感覺(jué)比以前的代碼簡(jiǎn)潔多了。
為什么呢盔腔？
仔細(xì)觀察杠茬，發(fā)現(xiàn)我思考 backtracking 經(jīng)常有個(gè)問(wèn)題。
什么時(shí)候截止 backtracking
比如這里弛随， level = 3 (0-3) 時(shí)澈蝙，就可以停止了，
但我需要在 level = 3時(shí)加判斷嗎撵幽？
不該灯荧，否則代碼會(huì)很復(fù)雜，和下部分代碼也有很多重復(fù)盐杂。
我應(yīng)該再下去一層逗载，這才是底層哆窿。
所以backtracking 每一層的物理意義是，
這一層厉斟，我檢驗(yàn)過(guò)了挚躯，ok, 沒(méi)問(wèn)題，下一層吧擦秽。
然后一層層下去码荔。
如果這一層有問(wèn)題，那么就返回感挥。
如果走到最后一層缩搅，發(fā)現(xiàn)沒(méi)有問(wèn)題了，那么就將最終結(jié)果插入到容器中触幼。
就是這么個(gè)過(guò)程硼瓣。
word pattern 2 也是如此。
還有就是置谦，backtracking 用 stringbuilder 時(shí)堂鲤，可以用 setLength
之類(lèi)的辦法快速清除下一層給這層帶來(lái)的變化。
還有個(gè)細(xì)節(jié)需要注意媒峡。當(dāng)截下來(lái)的數(shù)字瘟栖， > 255 或者，長(zhǎng)度大于1卻以0開(kāi)頭的話谅阿，都是無(wú)效的慢宗，直接 Ignore
Anyway, Good luck, Richardo! -- 09/19/2016
