LeetCode 93. 复原IP地址（回溯）

Michael阿明

发布于 2020-07-13 17:07:41

3020

发布于 2020-07-13 17:07:41

文章被收录于专栏：Michael阿明学习之路 Michael阿明学习之路Michael阿明学习之路

1. 题目

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/restore-ip-addresses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 回溯算法

相关题目：LeetCode 468. 验证IP地址

class Solution {
	vector<string> ans;
public:
    vector<string> restoreIpAddresses(string s) {
        if(s.size() < 4 || s.size() > 12)
        	return {};
        bt(s,1,0);//从第一个字符前面开始插入.
        return ans;
    }

    void bt(string &s, int idx, int count)
    {
    	if(count > 3)//3个.才行
    		return;
    	if(count == 3 && isIPv4(s))
    	{
    		ans.push_back(s);
    		return;
    	}
    	for(int i = idx; i < s.size(); ++i)
    	{
    		s.insert(i,".");
    		bt(s,i+2,count+1);//插入后，至少向后移动2个位置再插入新的.
    		s.erase(i,1);//回溯，删除1个字符 . 
    	}
    }

    bool isIPv4(string &IP)	//参考leetcode 468
    {
    	vector<string> part;
    	split(IP, part);
    	int s, i;
    	for(auto p : part)
    	{
    		s = 0;
    		if(p == "" || (p[0] == '0' && p.size() != 1))	//不能有前置0
    			return false;
    		for(i = 0; i < p.size(); ++i)
    		{
    			if(!isdigit(p[i]))
    				return false;
    			s = s*10+p[i]-'0';
    			if(s > 255)	//数字不能超范围
    			    return false;
    		}
    	}
    	return true;
    }

    void split(string &IP, vector<string> &part)
    {
    	string p;
    	for(int i = 0; i < IP.size(); ++i)
    	{
    		if((IP[i]=='.' || i == IP.size()-1))
    		{
    		    if(i == IP.size()-1)
    		        p += IP[i];
    			part.push_back(p);
    			p = "";
    		}
    		else
    			p += IP[i];
    	}
    }
};