首页 > 代码库 > Restore IP Addresses

Restore IP Addresses

2024-07-09 05:30:37   220人阅读

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地址的有效性，有4段，每段数值0~255；然后进行深度搜索，对字符串我们每次取一个、二个或三个字符组成以子字符串，如果符合IsValue函数，则保留这部分，再对剩下部分进行深度搜索，直到满足4断且正好将字符串搜索完。

class Solution {public:    bool IsValid(string &s,int start,int end)    {        int sum=0;        int num=1;        if(s[start]==‘0‘&&end-start>1)            return false;        for(int i=end-1;i>=start;i--)        {            sum+=(s[i]-‘0‘)*num;            num*=10;        }        if(sum>=0 && sum<=255)            return true;        return false;    }    void dfs(vector<string> &result,vector<string> &ip,string &s,int dep)    {        if(ip.size()==4)        {            if(dep==s.size())            {                string addr=ip[0];                for(int i=1;i<ip.size();i++)                {                    addr+="."+ip[i];                }                result.push_back(addr);                return;            }        }        for(int i=1;i<4;i++)        {            if(dep+i<=s.size()&&IsValid(s,dep,dep+i))            {                int left=s.size()-dep-i;                if(ip.size()+left/3.0>4)                    continue;                ip.push_back(s.substr(dep,i));                dfs(result,ip,s,dep+i);                ip.pop_back();            }        }    }    vector<string> restoreIpAddresses(string s) {        vector<string> result,ip;        result.clear();        ip.clear();        dfs(result,ip,s,0);        return result;    }};

 


联系
我们