博文中会简要介绍Leetcode P0093题目分析及解题思路。
“Restore IP Addresses”是一道比较简单的深度优先搜索问题，这里是回溯法。最核心的思路是把握住每个片段的长度作为每个节点的搜索范围（搜索面积），跟据不同片段长度可以很轻松地定位下一个搜索的起点。最后结束条件则是与片段个数和当前起点位置有关。
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 points 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.
以下是Java的题解代码实现。
class Solution {
public List<String> restoreIpAddresses(String s) {
if (s.length() < 4 || s.length() > 16)
return this.ipAddresses;
this.dfs(new ArrayList<>(), s, 0, 0);
return this.ipAddresses;
}
private List<String> ipAddresses = new ArrayList<>();
private void dfs(List<String> address, String s, int index, int segments) {
if (index >= s.length()) {
if (segments == 4)
this.ipAddresses.add(String.join(".", address));
return;
}
// 一个片段长度在1-3
for (int len=1; len<=3; ++len) {
// 片段长度不能溢出总长度
if (index+len > s.length())
continue;
String segment = s.substring(index, index+len);
// 长度超过1的片段，开头不能是0，且片段值要符合0-255
if ((segment.length() > 1 && segment.charAt(0) == '0')
|| Integer.parseInt(segment) < 0 || Integer.parseInt(segment) > 255)
continue;
address.add(segment);
this.dfs(address, s, index+len, segments+1);
address.remove(address.size()-1);
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
if (s.length() < 4 || s.length() > 16)
return this->ip_addresses;
vector<string> address;
this->Dfs(address, s, 0, 0);
return this->ip_addresses;
}
private:
vector<string> ip_addresses;
void Dfs(vector<string> &address, const string &s, int index, int segments) {
if (index >= s.length()) {
if (segments == 4) {
string addr = address[0]+"."+address[1]+"."+address[2]+"."+address[3];
this->ip_addresses.push_back(addr);
}
return;
}
// 一个片段长度在1-3
for (int len=1; len<=3; ++len) {
// 片段长度不能溢出总长度
if (index+len > s.length())
continue;
string segment = s.substr(index, len);
// 长度超过1的片段，开头不能是0，且片段值要符合0-255
if ((segment.length() > 1 && segment[0] == '0')
|| stoi(segment) < 0 || stoi(segment) > 255)
continue;
address.push_back(segment);
this->Dfs(address, s, index+len, segments+1);
address.pop_back();
}
}
};