93. Restore IP Addresses
1. Description
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.
2. Example
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”]
3. Constraints
- 0 <= s.length <= 3000
- s consists of digits only.
4. Solutions
My Accepted Solution
// backtracking
class Solution
{
private:
vector<string> result;
bool isIPPartValid(string i_part)
{
// 1. it should not have leading zero
// 2. its range is [0, 255]
return ((i_part.size() == 1 || i_part.front() != '0') && 0 <= stoi(i_part) && stoi(i_part) <= 255);
}
void getAddresses(string &i_address, string currentSolution, int partIndex, int addressIndex)
{
// partIndex -> [1, 4]
if(partIndex > 1) currentSolution.push_back('.');
if(partIndex == 4)
{
string part = i_address.substr(addressIndex);
if(isIPPartValid(part))
{
currentSolution += part;
result.push_back(currentSolution);
}
}
else
{
// the range of every part is [1, 256], so it will include 1 ~ 3 digits
for(int i = 1; i <= 3 && addressIndex + i < i_address.size(); i++)
{
string part = i_address.substr(addressIndex, i);
if(isIPPartValid(part))
{
getAddresses(i_address, currentSolution + part, partIndex + 1, addressIndex + i);
}
}
}
}
public:
// vector<string> restoreIpAddresses(string s)
vector<string> restoreIpAddresses(string &i_address)
{
// the ip addresses must have 4 parts, and the range of them is [0, 255]
if(i_address.size() < 4 || i_address.size() > 12) return vector<string>{};
string solution;
getAddresses(i_address, solution, 1, 0);
return result;
}
};