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

dfs+回溯，整体套用dfs思路(终止条件+单步搜索)，单步搜索以某个ip段进行搜索，满足[0,255]条件的缓存至临时变量temp中；

终止条件temp存满4个IP段，且s中的所有数字全部取完，则是有效结果。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串vector
     */
    vector<string> res;
    void dfs(string s, vector<string> temp, int index) {
        if (temp.size() == 4) { //可能结果过滤存储
            if (index == s.size())
                res.push_back(temp[0] + "." + temp[1] + "." + temp[2] + "." + temp[3]);
            return ;
        }

        for (int i = 1; i <= 3; i++) { //截取某一位的可能ip
            if (s.size() - index >= i) { //剩余数字还够截取某一位ip
                int num = atoi(s.substr(index, i).c_str());
                if (num >= 0 && num <= 9 && i == 1 ||
                        num >= 10 && num <= 99 && i == 2 ||
                        num >= 100 && num <= 255 && i == 3) {
                    temp.push_back(s.substr(index, i));
                    dfs(s, temp, index + i);
                    temp.pop_back();
                }
            } 
            else {
                break;
            }
        }

    }
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> temp;
        dfs(s, temp, 0);

        return res;
    }
};