93-复原IP地址

LeetCode 93. Restore IP Addresses

LeetCode-93

Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.

A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, “0.1.2.201” and “192.168.1.1” are valid IP addresses and “0.011.255.245”, “192.168.1.312” and “192.168@1.1” are invalid IP addresses.

Example 1:

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

Example 2:

Input: s = "1111"
Output: ["1.1.1.1"]

method: 回溯

substr(pos, len) 返回从pos开始的len个字符组成的字符串

---

1. str.erase(pos) 删除从pos开始的所有元素
2. str.erase(pos, num) 删除从pos开始的num个元素
3. st.erase(iterator) 删除迭代器指向的元素

---

1. str.insert(pos, string) 在pos的位置插入一个字符串
2. str.insert(iterator, char) 在迭代器指向的位置插入一个字符

---

类似于分割回文串，有些不同点：IP有效性，固定分割4块，直接在字符串上操作

IP地址有效性的判断：

• 不能有前导0
• 不能有特殊符号
• 不能超过255

vector<string> ret;
bool isValid(const string& s, int start, int end) {
    if (s[start] == '0' && start != end) return false;  // 不是单独的0
    int num = 0;
    for (int i = start; i <= end; ++i) {
        if (s[i] < '0' || s[i] > '9') return false; // 不能是其他字符
        num = num * 10 + (s[i] - '0');
        if (num > 255) return false;    // 不能超过255
    }
    return true;
}
void dfs(string& s, int index, int num) {
    if (num == 3) { // 插入3个点就可以结束了
        if (isValid(s, index, s.size() - 1)) {
            ret.push_back(s);
        }
        return;
    }
    for (int i = index; i < index + 3 && i < s.size() - 1; ++i) {
        if (isValid(s, index, i)) {
            s.insert(s.begin() + i + 1, '.');   // 在i+1的位置插入点
            dfs(s, i + 2, num + 1);     // 从i+2的位置继续遍历
            s.erase(s.begin() + i + 1); // 回溯删掉点
        }
        else break; // 如果这个点不行，后面也肯定不行
    }
}
vector<string> restoreIpAddresses(string s) {
    if (s.size() > 12) return ret;
    dfs(s, 0, 0);
    return ret;
}

进入for循环是要对index操作，还是对i操作要分清楚

• 递归结束条件：如果已经插入3个分割点了，后面的子串自动成为第4个地址，如果有效，直接可以保存了

因为只考虑3个分割点，所以不会在最末尾插入.，不然会出现1.1.11.，
所以判断条件是i < s.size() - 1
或者在有效性判断里边加上

if (start > end) return false;
此时 start = s.size()，end = s.size() - 1

分割回文串里面是这个分割点不行，换到下一个分割点，所以用continue
这里是如果这个分割点不行，再往后面肯定也不行，如256不行，再往后2561，25610肯定也不行，所以直接break

因为在第i个位置分割，所以在i+1的位置插入分割点，后面的遍历就要从i+2的位置开始