LeetCode Restore IP Addresses 恢复IP地址

Restore IP Addresses

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)

情况多得让人天旋地转的题目，非常繁琐，只能一个条件一个条件地满足了。

本题学了个新的函数：stoi；不过注意这个函数只能是转换int大小的，超过了int的边界就会溢出。跟我们用什么数据类型保存stoi的结果无关。

主要考验递归回溯和剪枝的真功夫了。看来这三个技能都是算法必修的，还要可以很灵活运用，否则这样的题目不可能做出来。

class Solution {
public:
	vector
  
    restoreIpAddresses(string s) 
	{
		vector
   
     vs; if (s.empty() || s.length()>12) return vs; restore(s, vs); return vs; } bool isLegalIPSec(string s) { //注意：数据太大会领导i溢出，所以别忘记加判断s.length()>3 if (s.empty() || s.length() > 3) return false; //注意：01,02,033等情况，但是0是合法的 if (s.length()>1 && s[0] == '0') return false; //因为stoi只能是转换成为int大小，超过INT_MIN INT_MAX就会溢出 int i = stoi(s); return i>=0 && i<=255; } void restore(string &s, vector
    
      &vs, string itmedia="", int num=1) { if (s.empty()) return; if (num == 4 && isLegalIPSec(s)) { itmedia += s; vs.push_back(itmedia); return; } else if (num == 4) return; //注意要加s.length()否则会在1111等四个字符中超标的 for (int i = 1; i < 4 && i