Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.
A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Example 1:
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]
Example 3:
Input: s = "1111"
Output: ["1.1.1.1"]
Example 4:
Input: s = "010010"
Output: ["0.10.0.10","0.100.1.0"]
Example 5:
Input: s = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Constraints:
- 0 <= s.length <= 3000
- s consists of digits only.
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
dfs(result, s, "",0,"",0);
return result;
}
private void dfs(List<String> result, String s, String temp, int curIndex, String curSum, int times) {
if (times < 4 && times > 0) {
temp = temp + curSum + '.';
curSum = "";
}else if (times == 4 && curIndex == s.length()) {
result.add(temp + curSum);
}
for (int i = curIndex; i < s.length() && times < 4; i++) {
curSum = curSum + s.charAt(i);
if (curSum.length() > 1 && curSum.startsWith("0") || Integer.parseInt(curSum) > 255){
break;
}
dfs(result, s, temp, i + 1, curSum, times + 1);
}
}
}动态规划
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
restore(s, 4, "", res);
return res;
}
public void restore(String s,int k,String out,List<String> res) {
if(k==0) {
if(s.isEmpty()){
res.add(out);
}
}else {
for (int i = 1; i <= 3; ++i) {
if(s.length() >= i && isValid(s.substring(0,i))) {
if(k==1){
restore(s.substring(i), k-1, out+s.substring(0,i), res);
}else{
restore(s.substring(i), k-1, out+s.substring(0,i)+".", res);
}
}
}
}
}
//校验函数：主要验证 每段数字是否为 001 022 等这样0开头的数字
public boolean isValid(String s) {
if(s.isEmpty() || s.length()>3 || (s.length()>1 && s.charAt(0)=='0')){
return false;
}else {
int resInt = Integer.parseInt(s);
return resInt<=255 && resInt>=0;
}
}
}本题考察回溯算法。本解法采用回溯算法，将ip分为4个字段，需要注意下面几点：
-
- 每个字段的值均不超过255，且不以0为开头（单独的0允许）,否则, 剪枝。
-
- 如果4个字段都加入到temp中之后，四个字段长度之和不等于s.length() - 1，那么不可加入到result中。