将一个数字串转化成合法IP,  DFS，注意一些细节

class Solution {public:    vector
    
      restoreIpAddresses(string s) {    	vector
     
       ans;        dfs(ans, s, "", 0, 0);        return ans;    }    void dfs(vector
      
        &ans, string s, string str, int pos, int dep) {        if (dep >= 4) {            if (dep == 4 && pos == s.length()) ans.push_back(str);        } else {            for (int i = pos; i < s.length(); i++) {                string sub = s.substr(pos, i-pos+1);                if (sub.length() <= 3 && stoi(sub) >= 0 && stoi(sub) <= 255 &&                    to_string(stoi(sub)) == sub) {                    string common = (dep == 3 ? "": ".");                    dfs(ans, s, str+sub+common, i+1, dep+1);                }            }        }    }        /**     * vector
       
         ans; //return all ips     * string s;    // input string     * string ip;   // 暂时存储     * string pos;  // 但前起始坐标     * string step; // ip地址中第几位数（4部分）     * 在一段 字符串 或 数组 上分段提取，使用 dfs, dfs 可以加入 剪枝     * 在这段数据上 搜索最小值，可以改成bfs     */    void dfs2(vector
        
          &ans, string s, string ip, int pos, int step)    {    	if(pos == s.length() && step == 4){    		//删除最后的点    		ans.push_back(ip.substr(0,ip.size()-1));    		return;    	}    	if(step > 4) return; //剪枝    	//  if(s.szie() - i > (4-step) * 3) return; //更快    	    	for(int i=pos+1; i<=s.size(); i++)    	{    		string tmp = s.substr(pos, i-pos);    		int val = stoi(tmp);    		//ip地址0-255之间， 并且 前面不能出现0（022）；    		// stoi(string) , to_string(int), char* = c_str(string)     		if(tmp.length() <=3 && val >=0 && val <= 255 && to_string(val) == tmp){    			dfs2(ans, s, ip+tmp+".",i,step+1);    		}    	}    }};