Restore IP Addresses问题及解法

本文主要是介绍Restore IP Addresses问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

示例:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

问题分析：

确定是否能组成有效的ip地址，在不违反连续性的前提下，我们可以采取回溯方法，依次尝试选取一个或者两个或者三个字符组成的数来作为每个ip地址的四分之一。

过程详见代码：

class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string> res;string ip="";bs(res, ip, 0, s, 0);return res;}void bs(vector<string>& res, string& ip, int start,string s,int n){if (ip.length() == s.length() + 4){string t = ip;t.pop_back();res.push_back(t);return;}else if (n >= 4) return;int i = start;int t;if(i < s.length()){t = s[i] - '0';ip.push_back(s[i]);ip.push_back('.');bs(res, ip, i + 1, s,n + 1);ip.pop_back();ip.pop_back();}if (i + 1 < s.length()){ t = (s[i] - '0') * 10 + s[i + 1] - '0';if(t >= 10){ip.push_back(s[i]);ip.push_back(s[i + 1]);ip.push_back('.');bs(res, ip, i + 2, s, n+ 1);ip.pop_back();ip.pop_back();ip.pop_back();}	}if (i + 2 < s.length()){t = (s[i] - '0') * 10 + s[i + 1] - '0';t = t * 10 + s[i + 2] - '0';if(t >=100 && t <=255){ip.push_back(s[i]);ip.push_back(s[i + 1]);ip.push_back(s[i + 2]);ip.push_back('.');bs(res, ip, i + 3, s, n + 1);ip.pop_back();ip.pop_back();ip.pop_back();ip.pop_back();	}    	}}
};

这篇关于Restore IP Addresses问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---