LeetCode 0093 - Restore IP Addresses
# Hints
模拟
DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
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:
consists of digits only.
# 题意
给定一个仅含数字 0-9
的字符串 ,可以在 中插入三个 .
字符将其转化为一个合法的 IP 地址,求所有可能的合法地址,答案可以以任意的顺序排列。
# 题解
按题意模拟,用 DFS 实现即可。
细节问题:
- 在递归时注意截断非法情况,若不及时剪枝会导致时间复杂度达到指数级,对于 的数据范围来说是不可接受的。
# AC代码
class Solution {
public:
vector<string> restoreIpAddresses(const string & s) {
// DFS
vector<string> vec;
vector<string> res;
dfs(0, 0, s, vec, res);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, int index, const string & s, vector<string> & vec, vector<string> & res) {
// 递归终止
if (depth == 4) {
assert(vec.size() == 4);
string ip;
for (int i = 0; i < vec.size(); i ++) {
ip += vec[i];
if (i != (int)vec.size() - 1) {
ip += '.';
}
}
res.push_back(ip);
return;
}
if (index >= s.length()) {
return;
}
// 递归
int val = 0;
for (int i = index; i < s.length(); i ++) {
val *= 10;
val += (s[i] - '0');
if (val > 255) {
break;
}
if (depth < 3 || i == (int)s.length() - 1) {
vec.push_back(s.substr(index, i - index + 1));
dfs(depth + 1, i + 1, s, vec, res);
vec.pop_back();
}
if (val == 0) {
break;
}
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01