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)
一刷
題解:
- 題目給定的restoreIpAddresses方法
這里我們首先確定要用到遞歸 + 回溯。 并且我們要了解,合理的ipv4地址是由4段組成窖剑,而且每一段的值都在 [0 烟央, 255] 之間
在這個(gè)方法里面,我們要做一些基本的邊界判斷,比如s 是否為null, s的length 是否在 4 和 12之間。
構(gòu)造好用來遞歸求解的方法restoreIp砍濒,確定好每個(gè)要用的參數(shù)。
返回結(jié)果
- restoreIp方法
這個(gè)方法是我們主要進(jìn)行處理和判斷的方法硫麻。我們也分為兩個(gè)部分
判斷并返回結(jié)果:
當(dāng)我們用來保存ip地址List ip長(zhǎng)度已經(jīng)等于4的時(shí)候
我們判斷記錄當(dāng)前position的int pos是否正好等于String s的長(zhǎng)度爸邢, 假如否,我們返回
否則拿愧,這時(shí)我們找到一個(gè)合理的解杠河。可以建立一個(gè)StringBuilder ipSb,重建出這個(gè)ip address感猛,將其加入結(jié)果集 res中七扰,返回
- 遞歸求解:
這里我們要從i = pos, 到i < s.length() && i < pos + 3來進(jìn)行遍歷陪白。 因?yàn)閕p每一部分最多只有3個(gè)digit颈走,所以我們有這個(gè)pos + 3的constraint
每次先求得當(dāng)前的ip segment = s.substring(i, pos + 1)
接下來進(jìn)行判斷, 調(diào)用isIpValid方法
假如當(dāng)前ip segment合理咱士, 我們將這段ip segment加入到list ip中
遞歸調(diào)用restoreIp(res, list, s, i + 1)進(jìn)行下一步求解
進(jìn)行回溯立由,去除掉之前加入的這段ip segment
否則我們?cè)黾觟,繼續(xù)嘗試下一個(gè)ip segment序厉, 直到i = pos + 3時(shí)跳出循環(huán)
- isIpValid方法
這個(gè)方法主要用來確定ip segment是否合理:
首先s為null或者""的時(shí)候返回false
當(dāng)s的首字符為'0'的時(shí)候锐膜,我們要判斷是否整個(gè)s為"0"。 假如是弛房,我們返回true道盏, 假如否,那么這次切割結(jié)果"0x"不合理文捶,我們返回false
求出ip segment的int值荷逞,然后返回這個(gè) ipInt是否 >= 0 并且 <= 255
粗略的時(shí)間和空間復(fù)雜度估計(jì)為O(2n),但因?yàn)橛泻芏嗟募糁Υ馀牛衧ubstring()种远,而且n的范圍是在4和12之間,所以詳細(xì)復(fù)雜度并不高顽耳,但也并不好算坠敷。
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if(s == null || s.length()<4 || s.length()>12) return res;
restoreIp(res, new ArrayList<>(), s, 0);
return res;
}
private void restoreIp(List<String> res, List<String> ip, String s, int pos){
if(ip.size() == 4){
if(pos!=s.length()) return;
//changeListToString
String ipString = changeListToString(ip);
res.add(ipString);
}
for(int i=pos; i<s.length() && i<pos+3; i++){//maximum is 3 char
String ipseg = s.substring(pos, i+1);
if(isValid(ipseg)){
ip.add(ipseg);
restoreIp(res, ip, s, i+1);
ip.remove(ip.size()-1);
}
}
}
private String changeListToString(List<String> ip){
StringBuilder sb = new StringBuilder();
for(String str : ip){
sb.append(str).append(".");
}
sb.setLength(sb.length()-1);
return sb.toString();
}
private boolean isValid(String s){
if(s == null || s.length() == 0) return false;
if(s.charAt(0) == '0') return s.equals("0");
int num = Integer.parseInt(s);
return (num>=0 && num<=255);
}
}
二刷
題解:
對(duì)于一個(gè)str和起始位置,從起始位置分別截取一段長(zhǎng)度為1射富,2膝迎,3的字串,然后進(jìn)入新的一輪dfs.
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if(s == null || s.length()<4 || s.length()>12) return res;
dfs(res, new ArrayList<>(), s, 0);
return res;
}
private void dfs(List<String> res, List<String> ip, String s, int pos){
if(ip.size() == 4){
if(pos!=s.length()) return;
//changeListToString
String ipString = changeListToString(ip);
res.add(ipString);
}
for(int i=pos; i<s.length() && i<pos+3; i++){
String ipseg = s.substring(pos, i+1);
if(isValid(ipseg)){
ip.add(ipseg);
dfs(res, ip, s, i+1);
ip.remove(ip.size()-1);
}
}
}
private String changeListToString(List<String> ip){
StringBuilder sb = new StringBuilder();
sb.append(ip.get(0));
for(int i=1; i<ip.size(); i++){
sb.append(".");
sb.append(ip.get(i));
}
return sb.toString();
}
private boolean isValid(String str){
if(str == null || str.length() == 0) return false;
if(str.charAt(0) == '0') return str.equals("0");
int num = Integer.parseInt(str);
return (num>=0 && num<=255);
}
}