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。
需要注意的是，以0开头的非零数字式非法的如1.010.1.1是无效的。
算法采用递归的思想，ip一共四组，每一组分别为一位，两位和三位，分别尝试：
class Solution {
public:int isValit(string s){int len=s.length();if(len>1 && s[0]=='0')return 0;int t=0,p=0;while(p<len){t=t*10+s[p]-'0';p++;}return t<=255;}void helper(string s,string str,int c,vector<string>&rest){int len=s.length();if(len<c || len>3*c)return;int sl=s.length();if(c==1){if(isValit(s)){str+=s;rest.push_back(str);return;}}else{if(sl>0 && isValit(s.substr(0,1)))helper(s.substr(1),str+s.substr(0,1)+".",c-1,rest);if(sl>1 && isValit(s.substr(0,2)))helper(s.substr(2),str+s.substr(0,2)+".",c-1,rest);if(sl>2 && isValit(s.substr(0,3)))helper(s.substr(3),str+s.substr(0,3)+".",c-1,rest);}return;}vector<string> restoreIpAddresses(string s) {vector<string>rest;string str="";helper(s,str,4,rest);return rest;}
};