题目: 给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能从 s 获得的有效IP 地址 。你可以按任何顺序返回答案。 有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。 例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。 1.输入:s = “25525511135” 输出:[“255.255.11.135”,“255.255.111.35”] 2.输入:s = “0000” 输出:[“0.0.0.0”] 3.输入:s = “1111” 输出:[“1.1.1.1”] 4.输入:s = “010010” 输出:[“0.10.0.10”,“0.100.1.0”]
0 <= s.length <= 3000 s 仅由数字组成 分析: IP地址特点是被3个‘.’字符分隔成4段,每段是0-255之间的数字。另外,除了“0”以外,其他数字不能以0开头。 下面逐个扫描输入字符串中的字符以恢复IP地址,针对字符串中的每个数字,通常有两个选项,第一个选项是将字符拼接到当前分段数字的末尾,并且保证拼接后的数字在0-255范围内。第二个选项是当前字符作为一个新的分段数字的开始。 如果输入的字符串的长度为n,由于逐一处理字符串的每个字符,因此需要n步,并且每一步都面临两个选项。 代码:
import java.util.LinkedList;
import java.util.List;
public class RestoreIpAddresses {
public static void main(String[] args) {
RestoreIpAddresses restoreIpAddresses = new RestoreIpAddresses();
List<String> strings = restoreIpAddresses.restoreIpAddresses("10203040");
System.out.println(strings);
}
public List<String> restoreIpAddresses(String s) {
LinkedList<String> result = new LinkedList<>();
helper(s,0,0,"","",result);
return result;
}
private void helper(String s, int i, int segI, String seg, String ip, LinkedList<String> result) {
if (i == s.length() && segI ==3 && isValidSeg(seg)){
result.add(ip+seg);
}else if(i < s.length() && segI <= 3){
char ch = s.charAt(i);
if (isValidSeg(seg+ch)){
helper(s,i+1,segI,seg+ch,ip,result);
}
if (seg.length() >0 &&segI<3){
helper(s,i+1,segI+1,""+ch,ip+seg+".",result);
}
}
}
private boolean isValidSeg(String seg) {
return Integer.valueOf(seg) <= 255&&(seg.equals("0")||seg.charAt(0)!='0');
}
}
|