数字字符串转换为IP地址

DFS+回溯，注意每一部分开头不能为0，如01是非法的，另外每一部分不能大于255：

//
// Created by jt on 2020/8/31.
//
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return string字符串vector
     */
    vector<string> restoreIpAddresses(string s) {
        // write code here
        vector<string> res;
        dfs(s, res, vector<string>());
        return res;
    }

    void dfs(string s, vector<string> &res, vector<string> tmp) {
        if (s.empty() && tmp.size() == 4) res.push_back(convert(tmp));
        for (int i = 1; i <= s.size(); ++i) {
            if (i > 1 && s[0] == '0') break;
            int val = stoi(s.substr(0, i));
            if (val > 255) break;
            tmp.push_back(s.substr(0, i));
            dfs(s.substr(i), res, tmp);
            tmp.pop_back();
        }
    }

    string convert(vector<string> vec) {
        string s;
        for (int i = 0; i < vec.size(); ++i) {
            s += vec[i];
            if (i != vec.size() - 1) s += '.';
        }
        return s;
    }
};