Accepted 4ms c++ solution use backtracking, easy understand.


  • 0
    class Solution {
    public:
        std::vector<std::string> restoreIpAddresses(std::string s) {
            std::vector<std::string> res;
    		std::string pre;
    		size = static_cast<int>(s.size());
    		restoreIpAddresses(res, s, pre, 0, 4);
    		return res;
        }
    private:
    	int size;
        void restoreIpAddresses(std::vector<std::string> &res, std::string &s, std::string pre, int pos, int point) {
    		if (size - pos < point || size - pos > 3 * point)
    			return;
    		if (pos == size) {
    			res.push_back(pre.substr(0, size + 3));
    			return;
    		}
    		for (int i = 1; i <= 3 && i + pos <= size; ++i) {
    			std::string str = s.substr(pos, i);
    			int num = std::stoi(str, NULL);
    			if (i == 1 || (i == 2 && num > 9) || (i == 3 && num > 99 && num < 256))
    				restoreIpAddresses(res, s, pre + str + ".", pos + i, point - 1); 
    		}
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.