Lq93：复原 IP 地址

68 阅读 0 评论 45 点赞

我是靠谱客的博主俊秀黑夜，最近开发中收集的这篇文章主要介绍Lq93：复原 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 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

思路：

以 "25525511135" 为例，第一步时我们有几种选择？
1. 选 "2" 作为第一个片段
2. 选 "25" 作为第一个片段
3. 选 "255" 作为第一个片段

能切三种不同的长度，切第二个片段时，又面临三种选择。
这会向下分支，形成一棵树，我们用 DFS 去遍历所有选择，必要时提前回溯。
因为某一步的选择可能是错的，得不到正确的结果，不要往下做了。撤销最后一个选择，回到选择前的状态，去试另一个选择。

回溯的要点：约束

约束条件限制了当前的选项，题中ip的格式就是约束条件：

一个片段的长度是1-3
片段的值的范围是0-255
不能是0X、0XX这种形式

用这些约束来进行充分的剪枝，去掉一些选择，避免搜索一不会产生正确答案的分支。

回溯的目标

目标决定了什么时候捕获答案，什么时候砍掉死支，回溯。
目标是生成 4 个有效片段，并且要耗尽 IP 的字符。
当条件满足时，说明生成了一个有效组合，加入解集，结束当前递归，继续探索别的分支。
如果满4个有效片段，但没耗尽字符，不是想要的解，不继续往下递归，提前回溯。

定义dfs函数

dfs 函数传什么？也就是，用什么描述一个节点的状态？
选择切出一个片段后，继续递归剩余子串。可以传子串，也可以传指针，加上当前的片段数组，描述节点的状态。
dfs 函数做的事：复原从 start 到末尾的子串。

/**
 * IP全排列组合问题
 */
class IPSolution
{
    List<String> res;
    List<String> temp;//temp用于将原字符串截取分成四段
    public List<String> restoreIpAddresses(String s)
    {
        int n = s.length();
        res = new ArrayList<>();
        temp = new ArrayList<>();
        if(n<=3 || n>=13)
        {
            return res;
        }
        dfs(s,0);
        return res;

    }
    public void dfs(String s,int begin)
    {
        if(begin==s.length() && temp.size()==4)
        {
            String str=temp.get(0);
            for(int i=1;i<4;i++)
            {
                str=str+'.'+temp.get(i);
            }
            res.add(str);
            return;
        }
        if(begin<s.length() && temp.size()==4)
        {
            return;
        }

        for(int len=1;len<=3;len++)
        {
            //保证后续s.substring(begin,begin+len)合法
            if(begin+len-1>=s.length())
            {
                return;
            }
            //剔除不合法的前导0
            if(len!=1 && s.charAt(begin)=='0')
            {
                return;
            }
            //截取字符串
            String st = s.substring(begin,begin+len);
            //截取的字符串长度为3时，大小不能超过255
            if(len==3 && Integer.parseInt(st)>255)
            {
                return;
            }
            temp.add(st);
            dfs(s,begin+len);
            temp.remove(temp.size()-1);
        }

    }

    public static void main(String[] args) {
        String s = "25525511135";
        IPSolution ipSolution = new IPSolution();
        System.out.println(ipSolution.restoreIpAddresses(s));
    }
}