LC93.复原IP地址todo

题目

思路

• 一定有提前剪枝的办法，但是这题数据量不大，所以不明显，希望下次有空想一想
• 回溯的树当中，往下多走一层，就多加一个.，每次去1位或2位或3位，意味着1个节点有3个孩子。
• 终止递归是2个条件，第1，起始位置超过总长度，第2，到达了最后一层。

  代码

class Solution {
public:
    bool checkFit(vector<string> cur_address, string origin_s) {
        int all_len = 0;
        for (string address: cur_address) {
            // 防止 023 这样的情况出现，读掉前置的0
            if (address[0] == '0' && address.size() > 1) {
                return false;
            }
            all_len += address.size();
            int cur_num = std::stoi(address);
            if (cur_num < 0 || cur_num > 255) {
                return false;
            }
        }
        return all_len == origin_s.size();
    }
    void backTrack(vector<vector<string>>& all_addresses, vector<string>& cur_address, string origin_s, int cur_depth, int& begin_pos) {
        // 还可以改剪枝条件，加快速度，但是我比较懒，所以不写了
        if (begin_pos > origin_s.size()) {
            return;
        }
        if (cur_depth == 4) {
            if (checkFit(cur_address, origin_s)) {
                all_addresses.push_back(cur_address);
            }
            return;
        }
        for (int frag_len = 1; frag_len <= 3; ++frag_len) {
            cur_address.push_back(origin_s.substr(begin_pos, frag_len));
            begin_pos += frag_len;
            backTrack(all_addresses, cur_address, origin_s, cur_depth + 1, begin_pos);
            begin_pos -= frag_len;
            cur_address.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<vector<string>> all_addresses;
        vector<string> cur_address;
        int begin_pos = 0;
        backTrack(all_addresses, cur_address, s, 0, begin_pos);
        vector<string> fit_addresses;
        for (vector<string> address: all_addresses) {
            string fit_address;
            for (string fragment_address: address) {
                fit_address += fragment_address;
                fit_address += '.';
            }
            // 去掉最后的一个 '.'
            fit_addresses.push_back(fit_address.substr(0, fit_address.size() - 1));
        }
        return fit_addresses;
    }
};