复原IP地址

谁践踏了优雅 2023-02-18 03:23 101阅读 0赞

## 一、前言 ##

问题来源LeetCode

问题链接：[https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1044/][https_leetcode-cn.com_explore_interview_card_bytedance_242_string_1044]

## 二、题目 ##

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

示例:

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

## 三、思路 ##

### 3.1 题意补充说明 ###

题意中有一点没有说明，输入的数值需要在输出都出现。例如：输入"010010"；输出\["0.1.0.10"\] 不满足要求，少了一个‘0’，也就是还原之后的字符串如果第一个是‘0’则长度只能为1，不能出现类似‘01’，‘01’转成数字之后是1，前面的0被省去了。

## 3.2 解法 ##

两种解法

方法一：递归解法，每往下走一步都带上上一步的结果

方法二：回溯法

### 3.3 举例说明 ###

输入：abcdefg，为输入的数组数字范围\[1,2\]，用字母方便区分。

**图解方法一：**

将上一步的结果集带到下一步，下一步如果有多种结果则和上一步结果进行结合，并将下一步的结果返回给上一步。如下图，结果集的第一步结果可能是a、ab、abc，对于第一步a，它的下一步可能是b、bc、bcd，后面步骤类似处理。直到最后一步。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

**图解方法二：**

从第一步到最后一步依次执行，不满足条件则返回继续下一步的执行，到最后一步，将满足条件的结果记录在结果集里。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

### 3.4 对比两种解法 ###

方法一，更符合人正常思考方式，但每往下走一步都需要拷贝一次上一步的结果集，执行效率不好。

方法二，对比方法一不需要进行数据拷贝，按照规则依次往下执行，当不满足条件返回到上一步，继续下一次循环，当走到最后一行并满足条件，将执行结果记录在结果集中。

### 3.5 总结 ###

方法一提供了一种将思考方式用编码实现，方法二是学习和理解回溯法的好例子。

## 四、编码实现 ##

//==========================================================================
    /**
    * @file    : 07_RestoreIpAddresses.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/106772470
    * @author  : niebingyu
    * @title   : 复原IP地址
    * @purpose : 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
    *
    * 示例 1:
    * 输入: "25525511135"
    * 输出:["255.255.11.135", "255.255.111.35"]
    *
    * 问题来源：力扣（LeetCode）
    * 链接：https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1044/
    */
    //==========================================================================
    #pragma once
    #include <vector>
    #include <iostream>
    #include <string>
    using namespace std;
    
    #define NAMESPACE_RESTOREIPADDRESSES namespace NAME_RESTOREIPADDRESSES {
    #define NAMESPACE_RESTOREIPADDRESSESEND }
    NAMESPACE_RESTOREIPADDRESSES
    
    
    #define NODECOUNT 4
    class Solution_1 
    {
    public:
        vector<string> restoreIpAddresses(string s) 
        {
            vector<vector<string>> temp;
            vector<vector<string>> ret = restoreIpAddresses(s, 0, NODECOUNT, temp);
            vector<string> result;
            for (int i = 0; i < ret.size(); ++i)
            {
                string str = "";
                if (ret[i].size() == NODECOUNT)
                {
                    for (int j = 0; j < NODECOUNT; ++j)
                    {
                        if (j == NODECOUNT - 1)
                            str += ret[i][j];
                        else
                            str += ret[i][j] + ".";
                    }
    
                    result.push_back(str);
                }
            }
    
            return result;
        }
    
        vector<vector<string>> restoreIpAddresses(string s, int pos, int n, vector<vector<string>> ret)
        {
            if (pos >= s.length() || n <= 0 || (int)s.length() - pos < n || (int)s.length() - pos > n * 3)
                return ret;
    
            vector<vector<string>> result;
            for (int i = 1; i <= 3 && i + pos <= s.length(); ++i)
            {
                vector<vector<string>> t = ret;
                if ((int)s.length() - pos - i < n - 1 || (int)s.length() - pos - i > (n - 1) * 3)
                    continue;
    
                string str = s.substr(pos, i);
                if (str[0] == '0' && str.length() != 1)
                    continue;
    
                int num = atol(str.c_str());
                if (num < 0 || num > 255)
                    break;
                
                if (n == NODECOUNT)
                {
                    vector<string> v;
                    v.push_back(str);
                    t.push_back(v);
                }
                else
                {
                    for (int j = 0; j < t.size(); ++j)
                    {
                        if (t[j].size() == NODECOUNT - n)
                            t[j].push_back(str);
                    }
                }
    
                vector<vector<string>> tp = restoreIpAddresses(s, pos + i, n - 1, t);
                result.insert(result.end(), tp.begin(), tp.end());
            }
    
            return result;
        }
    };
    
    class Solution_2
    {
    public:
        vector<string> restoreIpAddresses(string s)
        {
            //找3个.的位置,每个.之前组成的的数值必须要小于255，且以0开头的除非数字是0本身，否则也是非法
            vector<string> res;
            if (s.size() == 0 || s.size() < 4)    return res;
            vector<string> path;//存储从根开始的到叶子节点的满足条件的路径,因为最多3位数字一组，所以同一层横向循环时尝试最多3个位的长度
            dfs(s, 0, path, res);
            return res;
        }
    
    private:
        bool isValid(string ip)
        {
            int val = stoi(ip);
            if (val > 255)    return false;
            if (ip.size() >= 2 && ip[0] == '0')    return false;
            return true;
        }
    
        void dfs(string& s, int pos, vector<string>& path, vector<string>& res)
        {
            //首先判断剩余的位数，是不是还能满足要求，比如25525511135，若2.5.5.25511135显然不满足，这可以预判
            //4组，每组最多3位数字
            int maxLen = (4 - (int)path.size()) * 3;
            if (s.size() - pos > maxLen)    return;
            if (path.size() == 4 && pos == s.size()) 
            {
                string ans = "";
                for (int i = 0; i < 4; ++i) 
                {
                    ans += path[i];
                    if (i != 3)    ans += ".";
                }
    
                res.push_back(ans);
                return;
            }
    
            //回溯算法的典型模式，循环递归
            for (int i = pos; i < s.size() && i <= pos + 2; ++i) 
            {
                string ip = s.substr(pos, i - pos + 1);
                if (!isValid(ip))    continue;
                path.push_back(ip);
                dfs(s, i + 1, path, res);
                path.pop_back();
            }
        }
    };
    
    //
    // 测试 用例 START
    void test(const char* testName, string s, int expect)
    {
        Solution_1 S1;
        Solution_2 S2;
        vector<string> result1 = S1.restoreIpAddresses(s);
        vector<string> result2 = S2.restoreIpAddresses(s);
    
        // 粗略校验
        if (result1.size() == expect && result2.size() == expect)
            cout << testName << ", solution12 passed." << endl;
        else
            cout << testName << ", solution failed. result1:" << result1.size() << ", result2:" << result2.size() << " ,expect:" << expect << endl;
    }
    
    // 测试用例
    void Test1()
    {
        string s = "255255255255";
        int expect = 1;
    
        test("Test1()", s, expect);
    }
    
    // 测试用例
    void Test2()
    {
        string s = "25525511135";
        int expect = 2;
    
        test("Test1()", s, expect);
    }
    
    // 测试用例
    void Test3()
    {
        string s = "010010";
        int expect = 2;
    
        test("Test1()", s, expect);
    }
    
    NAMESPACE_RESTOREIPADDRESSESEND
    // 测试 用例 END
    //
    
    void RestoreIpAddresses_Test()
    {
    	NAME_RESTOREIPADDRESSES::Test1();
        NAME_RESTOREIPADDRESSES::Test2();
    	NAME_RESTOREIPADDRESSES::Test3();
    }

**执行结果：**

![20200615221827492.png][]

[https_leetcode-cn.com_explore_interview_card_bytedance_242_string_1044]: https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1044/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615221509141.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200615221549741.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200615221827492.png]: https://img-blog.csdnimg.cn/20200615221827492.png