[leetcode]93.复原IP地址

50 阅读 0 评论 33 点赞

我是靠谱客的博主细腻蜗牛，最近开发中收集的这篇文章主要介绍[leetcode]93.复原IP地址，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 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 地址。

示例 1：

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

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "1111"
输出：["1.1.1.1"]

示例 4：

输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]

示例 5：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

0 <= s.length <= 3000
s 仅由数字组成

思路：（来自leetcode题解）
dfs+回溯剪枝

在这里插入图片描述

1.递归参数

void dfs(string& s, int startIndex, int pointNum)

其中startIndex记录搜索的起始位置，pointNum记录添加’.‘的数量，s为已经添加了’.'的字符串。

递归终止条件：pointNum表示逗点数量，pointNum为3则说明字符串分成了4段，检测到pointNum为3的时候，验证一下剩余的字符串做第四段是否合法，如果合法就加入到结果集里面。

2.单层搜索

 for (int i = startIndex; i < s.size(); i++)

循环中 [startIndex,i]就是这个区间的字串，需要判断这个字串是否合法。
如果合法就在字符串后面加上符号.表示已经被分割。
如果不合法就结束本层循环。

然后就是递归和回溯的过程：
递归调用的时候，下一层递归的startIndex要从i+2开始（因为需要在字符串中加了分隔符），同时记录分割符的数量pointNum要+1.
回溯的时候，就将刚刚加入的分隔符删掉即可，pointNum也要-1。

3.判断字串是否合法

判断一个字串是否合法有以下三点：

段位为0开头的数字不合法。
段位里有非正整数字符不合法。
段位如果大于255不合法。

AC代码：

class Solution {
   public:
    vector<string> ans;  //记录结果
    void dfs(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isVaild(s, startIndex, s.size() - 1)) {
                //判断最后一段是否合法
                ans.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isVaild(s, startIndex, i)) {
                //判断s[startIndex,i]区间内是否合法
                s.insert(s.begin() + i + 1, '.');  //在i的后面插入一个点
                pointNum++;
                dfs(s, i + 2, pointNum);  //判断下一个段，插入之后下一个字串的起始位置位i+2
                pointNum--;
                s.erase(s.begin() + i + 1);  //回溯，擦掉之前添加的点
            } else {
                break;  //不合法直接结束
            }
        }
    }
    bool isVaild(const string& s, int start, int end) {
        //判断字符串s在左闭右闭区间[start,end]所组成的数字是否合法
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) {
            return false;  //出现前导0
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') {  //非法字符
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) {
                return false;  //超过界限
            }
        }
        return true;
    }
    vector<string> restoreIpAddresses(string s) {
        if (s.size() > 12) {
            return ans;
        }
        dfs(s, 0, 0);
        return ans;
    }
};