LeetCode 93. LeetCode93-复原IP地址-20200711-java
原题链接
中等
作者:
bmdxyn0725
,
2020-07-11 18:10:47
,
所有人可见
,
阅读 702
class Solution {
List<String> res = new ArrayList();
public List<String> restoreIpAddresses(String s) {
if(s==null || s.length() < 1 || s.length() > 12) return res;
// 参数2: 第i个数, 参数3: 第k个字符
dfs(s, 0, 0, "");
return res;
}
public void dfs(String s, int u, int k, String path){
if(k == s.length()){
if(u == 4){
res.add(path.substring(0, path.length()-1));
return;
}
}
if(u == 4) return;
for(int i = k, t = 0; i < s.length(); i++){
//有前导0时剪枝
if(i > k && s.charAt(i-1)-'0'==0 && t==0) return;
//每次把个位空出来, 将t*10即可
t = t * 10 + s.charAt(i) - '0';
if(t<=255){
dfs(s, u+1, i+1, path + t + ".");
}
}
}
}