LeetCode93—Restore IP Addresses

太过爱你忘了你带给我的痛 2022-08-21 01:09 177阅读 0赞

# LeetCode93—Restore IP Addresses #

类似路径搜索问题，IP地址每一小段的范围是0~255，对于输入的字串来说，考虑长度分别为1，2,3这三种情况。

## 原题 ##

> Given a string containing only digits, restore it by returning all possible valid IP address combinations.
> 
> For example:  
> Given “25525511135”,
> 
> return \[“255.255.11.135”, “255.255.111.35”\]. (Order does not matter)

## 分析 ##

想象一个树。一共四层，每一层代表ip地址的小段，每一层必须满足条件”0~255”（1位数到3位数），且不能出现”01” “024”这种首字母为0的情况。  
递归搜索结果，返回的条件：  
1. 收集满4段，并且每段有效  
2. 输入串s的字符全部用完  
对于第2个条件，我之前的想法是，当收集满4段之后，把这4段长度加起来与`s.size()`比较，后来网上看到一种更好的方法：让`s.size()`和`index`（递归变量）比较，这样效率更高，不用每次循环计算长度，均在代码中注释。

## 代码 ##

class Solution {
    private:
        bool valid(string s)
        {
            if (s.size() == 2)
            {
                if (s[0] == '0')//"01"情况排除
                    return false;
            }
            if (s.size() == 3)
            {
                if (s[0] == '0' || atoi(s.c_str()) > 255)//除了"001"还要排除大于255
                    return false;
            }
            return true;
        }
        void help(string s, int len, vector<string>& tmpRes, vector<string>&result, int index)
        {
            if (tmpRes.size() == 4)
            {
                //当满足条件时，s里面的字符肯定用完，i==s.size()-1，则index==i+1==s.size()
                if (index == s.size())
                {
                    string ip;
                    for (int i = 0; i < tmpRes.size(); i++)
                    {
                        ip += (tmpRes[i] + '.');
                    }
                    ip.pop_back();
                    result.push_back(ip);
                }
                return;
                //下述方法每次都计算ip的长度，效率较低
                /*
                string ip;
                for (int i = 0; i < tmpRes.size(); i++)
                {
                    ip += (tmpRes[i] + '.');
                }
                ip.pop_back();
                if (ip.size() == len + 3)
                {
                    result.push_back(ip);
                }
                else
                    return;
                    */
            }
            string str;
            for (int i = index; (i < len) && (str.size()<3); i++)
            {
                str.push_back(s[i]);
                if (valid(str))
                {
                    tmpRes.push_back(str);
                    help(s, len, tmpRes, result, i + 1);
                    tmpRes.pop_back();
                }
            }
        }
    public:
        vector<string> restoreIpAddresses(string s) {
            vector<string>result;
            vector<string>tmpRes;
            help(s, s.size(), tmpRes, result, 0);
            return result;
        }
    };