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"]

 

AC code:

class Solution {public:    vector
     
       restoreIpAddresses(string s) {        vector
      
        res;        helper(0, s, res, "", 0);        return res;    }        void helper(int count, string s, vector
       
        & res, string ret, int index) {        if (count > 4) return;        if (count == 4 && index == s.length())            res.push_back(ret);        for (int i = 1; i < 4; i++) {            if (index+i > s.length()) break;            string temp = s.substr(index, i);            if(temp[0] == '0' && temp.length() > 1 || atoi(temp.c_str()) > 255) continue;            string next = ret + temp;            helper(count+1, s, res, next+(count == 3 ? "" : "."), index+i);        }    }};
       
      
     

Runtime: 4 ms, faster than 23.68% of C++ online submissions for Restore IP Addresses.