93.复原IP地址

题目描述

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

示例：

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

暴力求解思路

1.暴力求解，注意检验转换后的长度即可。

Java代码实现

   public List<String> restoreIpAddresses(String s) {
        List<String> ips = new ArrayList<>();
        for (int i = 1; i < 4; i++) {
            for (int j = 1; j < 4; j++) {
                for (int k = 1; k < 4; k++) {
                    for (int l = 1; l < 4; l++) {
                        if (i + j + k + l == s.length()) {
                            int a = Integer.parseInt(s.substring(0, i));
                            int b = Integer.parseInt(s.substring(i, i + j));
                            int c = Integer.parseInt(s.substring(i + j, i + j + k));
                            int d = Integer.parseInt(s.substring(i + j + k));
                            if (a <= 255 && b <= 255
                                    && c <= 255 && d <= 255) {
                                String ip = a +"." + b + "." + c + "." + d;
                                if(ip.length() - 3 == s.length())
                                    ips.add(ip);
                            }
                        }
                    }
                }
            }
        }
        return ips;
    }

回溯法Java代码实现

public List<String> restoreIpAddresses(String s) {
        List<String> ips = new ArrayList<>();
        restoreIpAddresses(s,0,0,new StringBuffer(),ips);
        return ips;
    }

    /**
     * s : 字符串
     * point_count: 第几个点
     * point_index: 当前位置
     * curStr : 当前拼接结果
     * res : 结果集
     */
    private void restoreIpAddresses(String s,int point_count,int point_index,StringBuffer curStr,List<String> res){
        //递归结束条件
        if(point_count > 3)
            return;
        if(point_count == 3){
            if(s.substring(point_index).length() <= 3){
                int last = Integer.parseInt(s.substring(point_index));
                if(last <= 255){
                    int lastLen = curStr.length();
                    curStr.append(last);
                    if(curStr.length()  == s.length() + 3){
                        res.add(curStr.toString());
                    }
                    curStr.delete(lastLen,curStr.length());
                }
            }
            return;
        }

        for (int i = 1; i < 4 && (point_index+i < s.length()); i++) {
            int cur = Integer.parseInt(s.substring(point_index,point_index+i));
            if(cur <= 255){
                int lastLen = curStr.length();
                curStr.append(cur+".");
                restoreIpAddresses(s,point_count+1,point_index+i,curStr,res);
                curStr.delete(lastLen,curStr.length());
            }
        }
    }