题解 | #数字字符串转化成IP地址#

#include <string>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串vector
     */
    vector<string>result;
    vector<string> restoreIpAddresses(string s) {
        // write code here
        if (s.size()<4|| s.size() > 12) {
            return result;
        }
        searchIpAddresses(s, 0, 0);
        return result;
    }
  //每分割一个子串，都在分割的子串后面加点
    void searchIpAddresses(string& s, int start_index, int point_sum){
	  //终止条件
	  	//符合条件，收获结果
        if (point_sum==3) {
            if (isvalid(s, start_index,s.size()-1)) {
                    result.push_back(s);
            }
		  //不符合条件，直接返回上一个函数
            else {
                return ;
            }
        }

        for (int i=start_index; i<s.size(); i++) {
		  //判读分割的子串是否合法
            if (isvalid(s,start_index,i)) {
			  //合法的话在后面加点，点的数量point_sum+1
                s.insert(s.begin()+i+1, '.');
                point_sum++;
                searchIpAddresses(s,i+2,point_sum);
			  //回溯上一个状态分支
                s.erase(s.begin()+i+1);
                point_sum--;
            }  
		  //不符合直接退出
            else {
                break;
            }              
        }

    }
    bool isvalid(string s, int start_index, int end_index)
    {
        if (s[start_index]=='0'&&end_index>start_index) {
            return false;
        }
        else if (start_index>end_index) {
            return false;
        }
        int chartoint_sum=0;
        for(int i=start_index;i<=end_index;i++){
            chartoint_sum= chartoint_sum*10+(s[i]-'0');
        }
        if (chartoint_sum>255) {
            return false;
        }
        return true;
    }
};