20200810-93-复原IP地址.md

每天一道leetCode

信息卡片

• 时间：2020-08-10
• 题目链接：https://leetcode-cn.com/problems/restore-ip-addresses
• tag：回溯

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

有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

 

示例:

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

参考答案

暴力法

虽然看着是多层循环嵌套，但每个循环都很小，总体循环次数是3x3x3=27次

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        int len = s.length();
        for (int a = 1; a < 4; a++) {
            for (int b = 1; b < 4; b++) {
                for (int c = 1; c < 4; c++) {
                    if (a + b + c >= len || a + b + c < len - 3) {
                        continue;
                    }
                    int a1 = Integer.parseInt(s.substring(0, a));
                    int b1 = Integer.parseInt(s.substring(a, a + b));
                    int c1 = Integer.parseInt(s.substring(a + b, a + b + c));
                    int d1 = Integer.parseInt(s.substring(a + b + c));

                    if (a1 <= 255 && b1 <= 255 && c1 <= 255 && d1 <= 255) {
                        sb.append(a1).append(".").append(b1).append(".").append(c1).append(".").append(d1);
                        if (sb.length() == len + 3) {
                            result.add(sb.toString());
                        }
                        sb.delete(0, sb.length());
                    }
                }
            }
        }
        return result;
    }
}

回溯法

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        dfs(s, 0, new ArrayList<String>(), result);
        return result;
    }

    private void dfs(String s, int start, List<String> temp, List<String> result) {
        if (temp.size() == 4 && start == s.length()) {
            StringBuffer str = new StringBuffer();
            for (int i = 0; i < 3; i++) {
                str.append(temp.get(i)).append(".");
            }
            str.append(temp.get(3));
            result.add(str.toString());
            return;
        }
        if (temp.size() == 4 && start != s.length()) {
            return;
        }
        for (int i = 1; i < 4; i++) {
            if (start + i > s.length()) { return; }
            if (i > 1 && s.charAt(start) == '0') { return; }
            String str = s.substring(start, start + i);
            if (i == 3 && Integer.parseInt(str) > 255) { return; }
            temp.add(str);
            dfs(s, start + i, temp, result);
            temp.remove(temp.size() - 1);
        }
    }
}