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)----------------------------------------------------
DFS
class Solution { public: int stringToInt (string s) { int num = 0; for (int i = 0; i < s.length(); i++) { num = num * 10; int temp = s[i] - '0'; num = num + temp; } return num; } void rec (string cur, string s, int count, vector<string> &ret) { if (s.length() == 0 && count == 4) { ret.push_back(cur); }else if (count < 4 && s.length() != 0) { if (count != 0) { // no '.' before the first part cur = cur + "."; } string temp; if (s.length() >= 1) { temp = cur + s[0]; rec(temp,s.substr(1),count+1,ret); } if (s.length() >= 2 && s[0] != '0') { temp = cur + s.substr(0,2); rec(temp,s.substr(2),count+1,ret); } if (s.length() >= 3 && s[0] != '0') { temp = cur + s.substr(0,3); if (stringToInt(s.substr(0,3)) < 256) { rec(temp,s.substr(3),count+1,ret); } } } } vector<string> restoreIpAddresses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<string> ret; rec("",s,0,ret); return ret; } };Update on Sep-21-2014
Same algorithm but with index
class Solution { public: void rec(vector<string> &rt, string s, int index, int count,string ip) { if (count == 4 && index == s.length()) { rt.push_back(ip); return; } if (count > 4 || index > s.length()) return; if (count != 0) { ip += "."; } rec(rt,s,index + 1, count + 1, ip + s.substr(index,1)); if (index + 1 < s.length() && s[index] != '0') { string sub = s.substr(index,2); rec(rt,s,index + 2, count + 1, ip + sub); } if (index + 2 < s.length() && s[index] != '0') { string sub = s.substr(index,3); if (stoi(sub) < 256) { rec(rt,s,index + 3, count + 1, ip + sub); } } } vector<string> restoreIpAddresses(string s) { vector<string> rt; if (s == "") return rt; rec(rt,s,0,0,""); return rt; } };
No comments:
Post a Comment