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

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string path;
        dfs(s, 0, path, result);
        return result;
    }
    void dfs(const string& s, int index, string& path, vector<string>& result)
	{
	  //记录IP部分的个数，IP有效是4个部分,然后如果是4个部分了，将字符串分完了，说明有效
        if (index == 4 && s.empty()) {
            result.push_back(path);
            return;
        }
	  //如果此时分了四个部分，但是s还有多余的，说明没分完，这轮是无效的
        if (index >=4&&!s.empty())
            return;

	  //每一个部分一共就3个数字，因此取3个数字就是一个部分了
        for (int i = 1; i <= 3; i++) {
		  //如果字符串s是空的，就没必要了
            if (s.empty()) {
                break;
            }
		  //如果字符串s的大小少于能分的个数了，也没必要了
            if (s.size() < i)
                break;
		  //如果是一个字符串的首部，且该首部是0开头，后续就不能再是非0数了
            if (i != 1 && s[0] == '0') {
                break;
            }
		  //截取到i位置的数，作为这一部分的数
            string temp = s.substr(0, i);
            int num = std::stoi(temp);
            if (num >= 0 && num <= 255) {
			  //如果是index==0的 (也就是IP地址的第一部分)，就没必要插入'.',其余的才需要去插入'.'
                if (index != 0) {
                    path.push_back('.');
                }
			  //加入到路径的后面
                path.append(temp);
			  //继续dfs
                dfs(s.substr(i), index + 1, path, result);
              //回溯  
			  //如果index==0，说明这时回溯不需要考虑'.'，如果index!=0说明需要考虑'.'
			  if (index != 0)
                    path.resize(path.size() - i - 1);
                else
                    path.resize(path.size() - i);
            }
        }
    }
};