Skip to content

Instantly share code, notes, and snippets.

@s4553711
Created February 5, 2018 14:10
Show Gist options
  • Save s4553711/475afe56a81ed6385dd744e55ae9e6d7 to your computer and use it in GitHub Desktop.
Save s4553711/475afe56a81ed6385dd744e55ae9e6d7 to your computer and use it in GitHub Desktop.
class Solution {
private:
public:
void DFS(string s, int start, int step, string ip, vector<string>& ans) {
if (start == s.size() && step == 4) {
ip.erase(ip.end() - 1);
ans.push_back(ip);
return;
}
if (s.size()-start >(4-step)*3) return;
if (s.size()-start <(4-step)) return;
int num = 0;
for(int i = start; i < start + 3; i++) {
num = num*10 + (s[i] - '0');
if (num <= 255) {
ip += s[i];
DFS(s, i+1, step+1, ip+'.', ans);
}
if (num == 0) return;
}
}
vector<string> restoreIpAddresses(string s) {
if (s.size() == 0) return {};
vector<string> ans;
string ip;
DFS(s, 0, 0, ip, ans);
return ans;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment