Restore IP Addresses 426
Question
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Example
Given "25525511135", return
[ "255.255.11.135",
"255.255.111.35" ]
Order does not matter.
Solution
这道题其实是将字符串分割成4段,使得结果为合法的IP地址。要求返回所有合法IP地址,想到用递归。
合法的IP地址为:1)由4段组成 2)每一段长度为1到3 3)每一段如果不是0,不能以0开头,如01,00 4)每一段大小不能大于255
用一个result记录合法答案,用一个list纪录当前答案,start代表能够取值的起始位置。
当前段可以取start~start,start~start+1,start~start+2这几个字符串,然后递归求下一段。每次取值要检验取的字符串的合法性。
当取满4段时,看此时是否还有字符串剩下,没有则将4段拼成合法的IP地址
代码如下:
public class Solution {
/**
* @param s the IP string
* @return All possible valid IP addresses
*/
public ArrayList<String> restoreIpAddresses(String s) {
// Write your code here
ArrayList<String> result = new ArrayList<String>();
if(s == null || s.length() == 0){
return result;
}
ArrayList<String> list = new ArrayList<String>();
helper(s, result, list, 0);
return result;
}
private void helper(String s, ArrayList<String> result, ArrayList<String> list, int start){
if(list.size() == 4){
//分成4段后若还有字符串剩余则不合法
if(start != s.length()){
return;
}
//每一段后面加".",再将最后一个"."删去
StringBuilder sb = new StringBuilder();
for(String str : list){
sb.append(str);
sb.append(".");
}
sb.deleteCharAt(sb.length() - 1);
result.add(sb.toString());
return;
}
for(int i = 1; i <= 3 && start + i <= s.length(); i++){
//每一段长度不能超过3,同时如果超过了1位,则不能以0开头,如01
if(i != 1 && s.charAt(start) == '0'){
break;
}
//如果该段为3位,则要检验是否超过255
if(i == 3 && !isValid(s.substring(start, start + 3))){
break;
}
String temp = s.substring(start, start + i);
list.add(temp);
helper(s, result, list, start + i);
list.remove(list.size() - 1);
}
}
//合法IP的每一段都小于等于255
private boolean isValid(String s){
if(Integer.valueOf(s) > 255){
return false;
}
return true;
}
}