https://leetcode.com/problems/restore-ip-addresses/

1. Use recursion:

  1. //4 ms    6.7 MB
  3. class Solution {
  4. public:
  5.     vector<string> restoreIpAddresses(string s) {
  6.         vector<string> result;
  8.         //pickSub(result, s, "", 4);
  9.         pickSub(&result, s, "", 4);
  11.         return result;
  12.     }
  14.     //void pickSub(vector<string>& result, string s, string curr, int rest){
  15.     void pickSub(vector<string>* result, string s, string curr, int rest){
  17.         if(s.length() > rest*3)
  18.             return;
  20.         if(rest!=0 && rest!=4)
  21.             curr += ".";
  23.         if(rest == 0){
  24.             //result.push_back(curr);
  25.             result->push_back(curr);
  26.             return;
  27.         }
  29.         string s_l;
  30.         string s_r;
  32.         for(int i=1; i<=3; i++){
  33.             if(s.length()>=i){
  34.                 s_l = s.substr(0, i);
  35.                 if(s.length()>=i+1)
  36.                     s_r = s.substr(i);
  37.                 else
  38.                     s_r = "";
  40.                 if((stoi(s_l) <= 255) 
  41.                     && ((stoi(s_l) > 0 && (s_l[0] != '0'))
  42.                         || (stoi(s_l) == 0) && (s_l == "0"))){
  43.                     pickSub(result, s_r, curr + s_l, rest-1);
  44.                 }
  45.             }
  46.         }
  47.     }
  48. };