1、思路

针对字符串中的每个数字，都会面临两种选项：

• 将当前字符拼接到当前分段的末尾，且拼接后的字符串值应该在0 ~ 255之间；

• 将当前字符串作为一个新分段的开始。

2、代码

class Solution {
private:
    vector<string> res;

public:
    bool isValidSeg(string seg)     //判断当前分段是否合法
    {
        return stoi(seg) <= 255 && (seg == "0" || seg[0] != '0');
    }

    //五个参数分别为：原字符串，当前遍历下标，分段数，当前分段字符串，当前结果ip地址
    void dfs(string& s, int i, int segI, string seg, string ip)
    {
        if (i == s.length() && segI == 3)   //遍历完毕，且已经分为四段，存储当前结果
        {
            res.push_back(ip + seg);
        }
        else if (i < s.length())            //尚未遍历完毕
        {
            string tmp = seg + s[i];        //将当前字符拼接到当前分段末尾
            if (isValidSeg(tmp))            //当前分段合法，则递归进入下一层
            {
                dfs(s, i + 1, segI, tmp, ip);
            }

            if (seg.length() > 0 && segI < 3)   //开一个新分段
            {
                string str{s[i]};
                dfs(s, i + 1, segI + 1, str, ip + seg + ".");
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        if (s.empty()) return res;

        dfs(s, 0, 0, "", "");

        return res;
    }
};