Given a string s containing only digits, return all possible valid IP addresses that can be obtained from s. You can return them in any order.
A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single dots and cannot have leading zeros. For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses and "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.
Example 1:
Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"]
Example 2:
Input: s = "0000" Output: ["0.0.0.0"]
Example 3:
Input: s = "1111" Output: ["1.1.1.1"]
Example 4:
Input: s = "010010" Output: ["0.10.0.10","0.100.1.0"]
Example 5:
Input: s = "101023" Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Constraints:
0 <= s.length <= 3000sconsists of digits only.
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> ans;
if (s.size() > 12) {
return ans;
}
string sol;
helper(s, 0, sol, ans);
return ans;
}
void helper(string s, int idx, string sol, vector<string>& ans) {
if (idx == s.size()) {
if (isValid(sol)) {
ans.push_back(sol);
}
return;
}
for (int i = idx; i < s.size(); i++) {
string str = s.substr(idx, i - idx + 1);
if (digitCheck(str)) {
string tmp = sol;
if (sol.empty()) {
sol = str;
} else {
sol += "." + str;
}
helper(s, i + 1, sol, ans);
sol = tmp;
}
}
}
bool digitCheck(string str) {
if (str.size() == 0 || str.size() > 3) {
return false;
}
long digit = stol(str);
if (str.size() == 1) {
return (digit >= 0 && digit <= 9);
} else if (str.size() == 2) {
return (digit >= 10 && digit <= 99);
} else {
return (digit >= 100 && digit <= 255);
}
}
bool isValid(string str) {
if (str.size() == 0) {
return false;
}
vector<string> strList = split(str, '.');
if (strList.size() != 4) {
return false;
}
return digitCheck(strList[0]) && digitCheck(strList[1]) &&
digitCheck(strList[2]) && digitCheck(strList[3]);
}
vector<string> split(string str, char delim) {
vector<string> ans;
stringstream ss(str);
string tmp;
while (getline(ss, tmp, delim)) {
ans.push_back(tmp);
}
return ans;
}
};
========= 0 ms =========
class Solution {
private:
void helper(string s,vector<string>& temp,vector<string>& res,int length){
if(length==0 && temp.size() == 4){
string str = "";
str += (temp[0]+".");
str += (temp[1]+".");
str += (temp[2]+".");
str += (temp[3]);
res.push_back(str);
return;
}
else if(temp.size()==4 && length!=0) return;
else if(temp.size()!=4 && length==0) return;
for(int i=1;i<=3 && i<=length;i++){
string ts = s.substr(s.length()-length,i);
int num = stoi(ts);
if(num>=0 && num<=255 && (i==1 || ts[0]!='0')){
temp.push_back(ts);
helper(s,temp,res,length-i);
temp.pop_back();
}
}
}
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
vector<string> temp;
helper(s,temp,res,s.length());
return res;
}
};
No comments:
Post a Comment