复原 IP 地址

题目链接

复原 IP 地址

题目描述

注意点

• 1 <= s.length <= 20
• s 仅由数字组成
• 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0）

解答思路

• 深度优先遍历的思想，从头开始遍历s，对于任意一段IP地址，其值位于0~255之间，且不包含先导0，可以根据这些条件对该段IP地址进行剪枝，确认好该段IP地址后再继续向下遍历探索下一段IP地址的情况
• 当找到了4段IP地址后，还要判断是否遍历到s的最后一位，如果没有则不满足题意，直接退出

代码

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

    public void dfs(String s, int idx, List<String> res, List<String> list) {
        // 找到了4段ip地址
        if (list.size() == 4) {
            // s遍历完则满足规则，否则直接退出
            if (idx == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < list.size(); i++) {
                    sb.append(list.get(i)).append(".");
                }
                sb.deleteCharAt(sb.length() - 1);
                res.add(sb.toString());
            }
            return;
        }
        StringBuilder sb = new StringBuilder();
        while (idx < s.length()) {
            sb.append(s.charAt(idx));
            idx++;
            // 不能超过255
            if (Integer.parseInt(sb.toString()) > 255) {
                break;
            }
            list.add(sb.toString());
            dfs(s, idx, res, list);
            list.remove(list.size() - 1);
            // 不含有前导0
            if ("0".equals(sb.toString())) {
                break;
            }
        }
    }
}

关键点

• 深度优先遍历的思想
• 剪枝的情况
• 注意找到4段IP地址后判断s是否遍历完