Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:
Given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
class Solution {
public:
bool check(string s){
if(atoi(s.c_str()) > ) return false;
if(s.size() > && s[] == '')return false;
return true;
}
void dfs(string s, vector<string> &cur){
if(cur.size() == ){
if(s.size() >= &&check(s)){
cur.push_back(s);
res.push_back(cur[]+'.'+cur[]+'.'+cur[]+'.'+cur[]);
cur.pop_back();
}
return ;
} for(int i = ; i <= && i <= s.size(); i++){
string temp = s.substr(,i) ;
if(check(temp)){
cur.push_back(temp);
dfs(s.substr(i,s.size()-i),cur);
cur.pop_back();
}
} }
vector<string> restoreIpAddresses(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
res.clear();
if(s.size()> || s.size() <) return res;
vector<string> cur;
dfs(s,cur);
return res;
}
private:
vector<string> res;
};