93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

---

本题需要给一个数字字符串添加点号，使其成为一个合法的IP地址。
递归求解。首先设置两个数组kMinLen和kMaxLen，表示剩余字符串的最小/大长度，比如开始时step=0，则字符串的长度范围应该是[4,12]。

const vector<int> kMinLen = { 4, 3, 2, 1 };
const vector<int> kMaxLen = { 12, 9, 6, 3 };

然后递归的切当前字符串最多前3个字符，转成int，看是否<=255，如果是，则继续递归。直到step==4且没有剩余字符时，得到一个合法的IP地址。

完整代码如下：

const vector<int> kMinLen = { 4, 3, 2, 1 };
const vector<int> kMaxLen = { 12, 9, 6, 3 };
class Solution {
public:
    void work(vector<string>& ans, string cand, string left, int step)
    {
        if (step == 4) {
            if (left.size() == 0) {
                ans.push_back(cand);
            }
            return;
        }
        if (left.size() >= kMinLen[step] && left.size() <= kMaxLen[step]) {
            int border = min(3, int(left.size()));
            for (int l = 1; l <= border; l++) {
                string part_str = left.substr(0, l);
                if (part_str != "0" && part_str[0] == ‘0’)
                    continue; // 防止"010"这样的leading zero
                int part_int = atoi(part_str.c_str());
                if (part_int <= 255) {
                    string tmp = cand + left.substr(0, l);
                    if (step < 3)
                        tmp += ".";
                    work(ans, tmp, left.substr(l), step + 1);
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s)
    {
        vector<string> ans;
        string cand = "";
        work(ans, cand, s, 0);
        return ans;
    }
};

本代码提交AC，用时3MS。

二刷。使用数组保存ip地址更方便，代码如下：

class Solution {
public:
	void dfs(vector<string>& ans,vector<string>& cand, string &s, int idx) {
		if (cand.size() == 4 && idx == s.size()) {
			string ip = "";
			for (int i = 0; i < cand.size(); ++i) {
				ip = ip + cand[i] + ".";
			}
			ans.push_back(ip.substr(0, ip.size() - 1));
			return;
		}
		if (cand.size() == 4 && idx < s.size())return;
		if (cand.size() < 4 && idx >= s.size())return;
		for (int i = idx; i < s.size() && i < idx + 3; ++i) {
			string part = s.substr(idx, i - idx + 1);
			if (part[0] == '0'&&part.size() > 1)continue;
			int val = stoi(part);
			if (val <= 255) {
				cand.push_back(part);
				dfs(ans, cand, s, i + 1);
				cand.pop_back();
			}
		}
	}
	vector<string> restoreIpAddresses(string s) {
		vector<string> ans;
		vector<string> cand;
		dfs(ans, cand, s, 0);
		return ans;
	}
};

本代码提交AC，用时0MS。