LeetCode #93

# Description:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

## Example:

``````For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
``````

# Code:

Method 1 Backtrack的做法。中间结果用一个string存，每次递归用同一个string。

``````class Solution {
public:
vector<string> result;
string ip;
DFS(s, 0, 0, ip, result);
return result;
}

void DFS(const string& s, int loc, int step, string& ip, vector<string>& result){
if(loc==s.size() && step==4){
result.push_back(ip.substr(0, ip.size()-1));
return;
}

if(s.size() - loc > (4-step)*3)
return;

if(s.size() - loc < (4-step))
return;

int num=0;
int sub_len=0;
for(int i=loc; i<loc+3; ++i){
num = num*10 + (s[i] - '0');

if(num<=255){ // 当前结点合法，则继续往下递归
sub_len++;
ip += s[i];
ip += '.';
// cout<<"step "<<step<<' '<<ip<<' '<<num<<endl;
DFS(s, i+1, step+1, ip, result);
ip.pop_back();  // Backtrack '.'
}
if(num==0) break; // 不允许前缀 0，但允许单个 0
}

ip.erase(ip.size()-sub_len, sub_len); // Backtrack 当前的sub string
}
};
``````

Method 2 不是backtrack的做法。中间结果用一个string存，每次递归用复制这个string。

``````class Solution {
public:
vector<string> result;
string ip;
DFS(s, 0, 0, ip, result);
return result;
}

void DFS(string s, int loc, int step, string ip, vector<string>& result){
if(loc==s.size() && step==4){
result.push_back(ip.substr(0, ip.size()-1));
return;
}

if(s.size() - loc > (4-step)*3)
return;
if(s.size() - loc < (4-step))
return;

int num=0;
for(int i=loc; i<loc+3; ++i){
num = num*10 + (s[i] - '0');

if(num<=255){
ip += s[i];
DFS(s, i+1, step+1, ip+'.', result);
}
if(num==0) break;
}

}
};
``````