LeetCode 93 复原 IP 地址 - 回溯解法

每回拿到的长度应该为 1-3
for(int len = 1;len<=3;len++){ 这里可能 index+len>max 也要限制一下
	left = loc.substr(index,len)
	if(left 合法){
		path.push(left)
		add_path(index+len)
		path.pop();
	}
}

返回条件和  回文串 一样
当前面都加到 path 中后, 此时就应该返回了.

class Solution {

public:

    vector<string> path;

    vector<string> result;

    string loc_string;

    void add_path(int index) {

        if (path.size() > 4)

            return;

        if (index == loc_string.size() && path.size() == 4) {

            string tmp = path[0];

            for (int i = 1; i < 4; ++i) {

                tmp += '.' + path[i];

            }

            result.push_back(tmp);

            return;

        }

        for (int len = 1; len <= 3 && index + len <= loc_string.size(); len++) {

            string left = loc_string.substr(index, len);

            if (left[0] == '0' && len > 1) {
				// 这里 一旦触发 continue  后面的循环一定会continue, 可以直接 break.
                continue;

            }

            if(stoi(left)>255) break;

            path.push_back(left);

            add_path(index + len);

            path.pop_back();

        }

    }

    vector<string> restoreIpAddresses(string s) {

        loc_string = s;

        add_path(0);

        return result;

    }

};