93.Restore IP Addresses

Tags: String Backtracking Medium

Links: https://leetcode.com/problems/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"]

---

class Solution {
    bool check(string & s)
    {
        if (stol(s) - 255 > 0) return false;
        if (s.size() > 1 && s[0] == '0') return false;

        return true;
    }

public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        int n = s.size();

        if (n < 4 || n > 12) return result;

        for (int i = 1; i <= 3; ++i){
            for (int j = 1; j <= 3; ++j){
                for (int k = 1; k <= 3; ++k){
                    int m = n - (i + j + k);
                    if (m > 0 && m <= 3){
                        string s1 = s.substr(0, i), s2 = s.substr(i, j), s3 = s.substr(i + j, k), s4 = s.substr(i + j + k, n);
                        if (check(s1) && check(s2) && check(s3) && check(s4)){
                            string tmp = s1+ "." + s2 + "." + s3 + "." + s4;
                            result.push_back(tmp);
                        }
                    }
                }

            }
        }

        return result;
    }
};

直接暴力求解，注意特殊的例子来完善check函数，如"010010"， 以及长度特别长超过12位的情况。在《算法手写代码手册C++》里把此题归为利用DFS求解。确实可以用DFS求解，但是显然无论如何设计仍然避免不了三次循环，优化的地方就是剪枝。

第二次我在程序20和21行做了一定修改，从原来的之判断m >0增加了一个判断条件，立刻速度最快了。

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Restore IP Addresses.
Memory Usage: 8.5 MB, less than 91.67% of C++ online submissions for Restore IP Addresses.