IP地址划分

问题陈述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

思路分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution{
    //主函数
    public List<Integer> restoreIPAdress(String s){
        List<String> address=new ArrayList<>();
        StringBuilder res=new StringBuilder();
        doRestore(0,address,res,s);
        return address;
    }
    //回溯框架
    private void doRestore(int k,List<String> address,StringBuilder res,String s){
        //base case
        if(k==4||s.length()==0){
            if(k==4&&s.length()==0){
                address.add(res.toString());
            }
            return;//注意此处有return。
        }
        //选择
        for(int i=0;i<s.length()&&i<=2;i++){//i<=2是因为ip地址范围0-255
            if(i!=0&&s.charAt(0)=='0'){
                break;//ip地址除第一位外其他位起始不能为0
            }
            String part=s.subString(0,i+1);
            if(Integer.valueOf(part)<=255){
                if(res.length()!=0){
                    part="."+part;
                    res.append(part);
                }
            doRestore(k + 1, addresses,res, s.substring(i + 1));
            res.delete(res.length() - part.length(), res.length());
            }
        }
        //穷举
        //撤销
        
    }
}