LeetCode 93. 複原IP位址（回溯）

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];
    	}
    }
};           

複制